grid47 Exploring patterns and algorithms
Nov 5, 2024
6 min read
Solution to LeetCode 20: Valid Parentheses Problem
You are given a string containing characters representing various types of brackets: ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’. Your task is to determine if the input string is valid. A string is considered valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
Problem
Approach
Steps
Complexity
Input: The input consists of a string s containing only the characters '(', ')', '{', '}', '[' and ']'.
Example: s = '({[]})'
Constraints:
• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.
Output: The output is a boolean value: true if the string is valid, otherwise false.
Example: true
Constraints:
• The result should be a boolean indicating whether the input string is valid.
Goal: To check whether the string contains valid parentheses by ensuring each open bracket has a corresponding and correctly ordered closing bracket.
Steps:
• Initialize an empty stack to keep track of open brackets.
• Iterate through each character in the string.
• If the character is an open bracket ('(', '{', or '['), push it onto the stack.
• If the character is a closing bracket (')', '}', or ']'), check if the stack is not empty and if the top of the stack matches the corresponding open bracket.
• If there's a match, pop the stack, else return false.
• After iterating through the string, if the stack is empty, return true (valid). Otherwise, return false (invalid).
Goal: Conditions that the input string will always meet.
Steps:
• The input string will only contain characters from '(', ')', '{', '}', '[' and '].
Assumptions:
• The input string is always non-empty.
• The input string contains only valid characters.
• Input: s = '({[]})'
• Explanation: This string contains balanced brackets: each opening bracket has a corresponding closing bracket in the correct order. Thus, the output is true.
• Input: s = '({[})'
• Explanation: This string contains mismatched brackets. The order is incorrect, and the closing bracket doesn't match the last opening bracket, so the output is false.
• Input: s = '([])'
• Explanation: This string contains balanced brackets: each opening bracket has a corresponding closing bracket in the correct order. Thus, the output is true.
Approach: The approach to solve this problem is by using a stack to ensure that each open bracket has a corresponding closing bracket in the correct order.
Observations:
• Using a stack data structure helps ensure the correct order of opening and closing brackets.
• Each closing bracket should match the most recent open bracket.
• By pushing open brackets onto the stack and popping them when encountering matching closing brackets, we can validate the string efficiently.
Steps:
• Initialize an empty stack to keep track of open brackets.
• Traverse the string from left to right.
• For each character, if it's an open bracket, push it onto the stack.
• If it's a closing bracket, check if the stack is not empty and if the top of the stack matches the corresponding open bracket. If so, pop the stack, otherwise return false.
• Finally, after processing all characters, return true if the stack is empty, indicating all brackets were properly matched.
Empty Inputs:
• The input string will never be empty. There will always be at least one bracket.
Large Inputs:
• The solution handles strings of length up to 10^4 efficiently.
Special Values:
• Handles cases with a single pair of brackets as well as very large balanced or unbalanced sequences.
Constraints:
• The solution must work for all strings of valid length and with valid bracket characters.
If 'x' is a closing bracket ')' and the stack is not empty and the top element of the stack is an opening bracket '(', then the top element is popped from the stack.
If 'x' is a closing bracket '}' and the stack is not empty and the top element of the stack is an opening bracket '{', then the top element is popped from the stack.
If 'x' is a closing bracket ']' and the stack is not empty and the top element of the stack is an opening bracket '[', then the top element is popped from the stack.
10 : Return
elsereturnfalse;
If none of the above conditions are met, it means there's an unmatched closing bracket, and the function returns false.
11 : Return
return stk.empty();
If the loop completes without returning false, it means all brackets are matched. The function returns true if the stack is empty, indicating that all brackets have been paired.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We iterate through the string once, performing constant time operations for each character.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) in the worst case when all characters are opening brackets.
