20. Valid Parentheses
Given a string 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.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
Solution
class Solution:
def isValid(self, s: str) -> bool:
mapping = {
")": "(",
"}": "{",
"]": "["
}
stack = []
for c in s:
if c not in mapping:
# we're at an opening bracket
stack.append(c)
else:
# we're at closing bracket
if len(stack) > 0 and mapping[c] == stack[-1]:
stack.pop()
else:
return False
if len(stack):
return False
return True
This solution works in ordern O(n) time using one loop and a stack.
We go through this string one character at a time. If we’re at an opening bracket, there is nothing that we need to do right now, because we’ll come back to it and process it later. So, we add it to the stack and carry on.
If we arrive at a closing bracket, however, we have to do some checking. We have to make sure that the most recent bracket that we processed matches the current bracket. For example, if we arrive at a closing square bracket ], then we want to make sure that the last thing we added to the stack is a matching [. If the last bracket doesn’t match, or if there is nothing else in the stack, we know that we have an invalid expression and return False.
Once we’ve processed the whole string, we make sure there is nothing left in the stack. If the stack is not empty, then that means we had brackets that were unmatched, and we return False.