Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is 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.
LeetCode Solutions1 <= s.length <= 104s consists of parentheses only '()[]{}'.Each replacement pass scans the entire string in , and in the worst case (e.g., "(((...)))") we need passes to fully reduce the string, giving overall.
Each string replacement creates a new string of up to characters.
The brute force approach repeatedly removes all adjacent matching pairs of brackets from the string until no more valid pairs remain. In each iteration, we replace (), [], and {} with empty strings; if the resulting string is eventually empty, all brackets were properly matched and nested. If the string is non-empty after no more replacements can be made, some brackets are unmatched or incorrectly ordered.
We iterate through the string exactly once, performing hash map lookups and stack operations at each step.
In the worst case (all opening brackets, e.g., "((([[["), the stack holds up to n elements.
We use a stack and a hash map that maps each opening bracket to its expected closing bracket. As we iterate through the string, when we encounter an opening bracket, we push its corresponding closing bracket onto the stack. When we encounter a closing bracket, we check if it matches the top of the stack — if not, or if the stack is empty, the brackets are incorrectly nested and we return false. After processing all characters, the string is valid only if the stack is empty.
We iterate through the string exactly once, performing hash map lookups and stack operations at each step.
In the worst case (all opening brackets, e.g., "((([[["), the stack holds up to n elements.
This approach is the inverted variant of Solution 2: instead of mapping opening brackets to expected closing brackets, we use a hash map that maps each closing bracket to its corresponding opening bracket, and push the actual opening brackets onto the stack. When we encounter a closing bracket, we check if the top of the stack is its matching opening bracket — if it matches we pop it, otherwise we return false. At the end, the string is valid only if the stack is empty.
We iterate through the string exactly once, performing stack operations and constant-time conditional checks at each step.
In the worst case (all opening brackets, e.g., "((([[["), the stack holds up to n elements.
This approach stores opening brackets on the stack (as in Solution 3) but eliminates the hash map entirely by using explicit conditional checks to verify bracket pairs. When we encounter an opening bracket it is pushed onto the stack; when we encounter a closing bracket we pop the top and directly compare it against the expected opening bracket using a series of if conditions. The string is valid only if the stack is empty after all characters have been processed.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Brute Force | Simple to understand and implement | Inefficient — repeatedly scans the string, leading to time | |||
| Stack store closing brackets | Classic interview approach; pushing the expected closing bracket makes the match check trivial | Requires a hash map in addition to the stack | |||
| Stack store opening brackets | Hash map lookup only happens at closing brackets; slightly fewer stack operations on average | Inverted map direction is slightly less intuitive to derive from scratch | |||
| Stack without hash map | No hash map needed — simpler memory footprint | Explicit conditional checks are more verbose and harder to extend to new bracket types |
Both Solution 2: Stack store closing brackets and Solution 3: Stack store opening brackets are optimal, both achieving time complexity and space complexity. The key difference is in the hash map direction: Solution 2 pushes the expected closing bracket onto the stack (so the check at each closing bracket is a direct equality), while Solution 3 pushes the actual opening bracket and looks up the match at closing time. Both are equally valid in interviews — Solution 2 is slightly more intuitive to explain, while Solution 3 more closely mirrors the natural reading of "does this closing bracket match what's on the stack?" Solution 4 achieves the same time complexity without a hash map but uses verbose conditional checks that are harder to extend.
class Solution: def isValid(self, s: str) -> bool: # Remove all pairs of valid parentheses until there are none left while '()' in s or '[]' in s or '{}' in s: s = s.replace('()', '').replace('[]', '').replace('{}', '')
return not sclass Solution: def isValid(self, s: str) -> bool: hash_map = {")": "(", "}": "{", "]": "["}
stack = []
for char in s: if char in hash_map: if stack and stack[-1] == hash_map[char]: # If the current character is a closing bracket, we check if the top of the stack is the corresponding opening bracket. If it is, we pop the top of the stack. If it isn't, or if the stack is empty when we encounter a closing bracket, then the string is not valid. stack.pop() else: return False else: # If the current character is an opening bracket, we push it onto the stack stack.append(char)
return not stack