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:
<strong>Input:</strong> "()" <strong>Output:</strong> true
Example 2:
<strong>Input:</strong> "()[]{}"
<strong>Output:</strong> true
Example 3:
<strong>Input:</strong> "(]" <strong>Output:</strong> false
Example 4:
<strong>Input:</strong> "([)]" <strong>Output:</strong> false
Example 5:
<strong>Input:</strong> "{[]}"
<strong>Output:</strong> true
解法
class Solution:
def isValid(self, s: 'str') -> 'bool':
dict_data={')':'(','}':'{',']':'['}
left=set(['(','{','['])
right=set([')','}',']'])
tmp_list=[]
for x in s:
if x in left:
tmp_list.append(x)
else:
tmp=dict_data[x]
if len(tmp_list)<1 or tmp_list[-1]!=tmp:
return False
tmp_list.pop()
if tmp_list:
return False
return True
