Valid Parentheses

Difficulty: Easy | Acceptance: 44.10% | Paid: No Topics: String, Stack

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.

• Examples
• Constraints
• Stack
• Hash Map Optimization
• String Replacement

Examples

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

Constraints

1 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.

Stack

Intuition We can iterate through the string and push every opening bracket onto a stack. When we encounter a closing bracket, we check if the top of the stack contains the corresponding opening bracket. If it does, we pop the stack; otherwise, the string is invalid.

Steps

• Initialize an empty stack.
• Iterate through each character in the string.
• If the character is an opening bracket (’(’, ’{’, ’[’), push it onto the stack.
• If the character is a closing bracket (’)’, ’}’, ’]’):
  • If the stack is empty, return false (no matching opening bracket).
  • Pop the top element from the stack.
  • If the popped element does not match the corresponding opening bracket for the current closing bracket, return false.
• After processing all characters, if the stack is empty, return true; otherwise, return false.

class Solution:\n    def isValid(self, s: str) -> bool:\n        stack = []\n        mapping = {')': '(', '}': '{', ']': '['}\n        \n        for char in s:\n            if char in mapping:\n                if not stack:\n                    return False\n                top_element = stack.pop()\n                if mapping[char] != top_element:\n                    return False\n            else:\n                stack.append(char)\n        \n        return not stack\n

Complexity

• Time: O(n)
• Space: O(n)
• Notes: We iterate through the string once, and in the worst case, we push all characters onto the stack.

Hash Map Optimization

Intuition This approach is conceptually similar to the standard stack approach but optimizes the matching logic by using a hash map to store the pairs of parentheses. This makes the code cleaner and the lookup for the matching opening bracket O(1).

Steps

• Create a hash map that maps closing brackets to their corresponding opening brackets.
• Initialize an empty stack.
• Iterate through the string.
• If the character is a closing bracket (exists in the map):
  • Check if the stack is not empty and the top of the stack matches the value from the map.
  • If not, return false.
  • If it matches, pop the stack.
• If the character is an opening bracket, push it onto the stack.
• Finally, return true if the stack is empty.

class Solution:\n    def isValid(self, s: str) -> bool:\n        stack = []\n        mapping = {')': '(', '}': '{', ']': '['}\n        \n        for char in s:\n            if char in mapping:\n                top_element = stack.pop() if stack else '#'\n                if mapping[char] != top_element:\n                    return False\n            else:\n                stack.append(char)\n        \n        return not stack\n

Complexity

• Time: O(n)
• Space: O(n)
• Notes: The space complexity is O(n) for the stack in the worst case. The hash map adds constant space O(1).

String Replacement

Intuition We can repeatedly remove all valid adjacent pairs of parentheses (”()”, ”[]”, ”{}”) from the string. If the string is valid, we will eventually be left with an empty string. If the string is invalid, some characters will remain.

Steps

• While the string contains ”()”, ”[]”, or ”{}“:
  • Replace all occurrences of ”()” with an empty string.
  • Replace all occurrences of ”[]” with an empty string.
  • Replace all occurrences of ”{}” with an empty string.
• Check if the resulting string is empty.

class Solution:\n    def isValid(self, s: str) -> bool:\n        while '()' in s or '[]' in s or '{}' in s:\n            s = s.replace('()', '').replace('[]', '').replace('{}', '')\n        return s == ''\n

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: In the worst case (e.g., ”(((((”), we might iterate through the string n times, resulting in quadratic time complexity. This is generally less efficient than the stack approach.