题目
Imagine you are building a compiler. Before running any code, the compiler must check that the parentheses in the program are balanced. Every opening bracket must have a corresponding closing bracket. We can approximate this using strings.
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets are closed by the same type of brackets.
- Open brackets are closed in the correct order.
- Note that an empty string is also considered valid.
Example:
Input: "((()))"
Output: True
Input: "[()]{}"
Output: True
Input: "({[)]"
Output: False
分析
创建一个栈。
然后开始从左到右枚举每个字符,
遇到左括号则进栈;
遇到右括号,则出栈栈顶的元素。判断该元素是否和当前的右括号匹配:
如不匹配,则返回 false.
如匹配,则继续下一个循环;
判断栈是否为空。为空则返回 true, 否则返回 false.
时间复杂度为 O(n).
代码
class Solution:
def isValid(self, s):
stack = []
matches = {
"}": "{",
"]": "[",
")": "("
}
for c in s:
if c in matches.values(): # 左括号
stack.append(c)
elif c in matches.keys(): # 右括号
left = stack.pop()
if left == matches[c]:
continue
else:
return False
else:
continue
return len(stack) == 0
# Test Program
s = "()(){(())"
# should return False
print(Solution().isValid(s))
s = ""
# should return True
print(Solution().isValid(s))
s = "([{}])()"
# should return True
print(Solution().isValid(s))