動機
複習stack
Problem
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.
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 <= 104
s
consists of parentheses only'()[]{}'
.
Sol
class Solution:
def isValid(self, s: str) -> bool:
stk = []
tbl = {"(":")", "[":"]","{":"}"}
lefts = list(tbl.keys())
for c in s:
if c in lefts:
stk.append(c)
elif len(stk) > 0 and tbl[stk[-1]] == c:
stk.pop()
else:
return False
return len(stk) == 0