<div>
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:
<pre>Input: s = "()" Output: true </pre>
Example 2:
<pre>Input: s = "()[]{}" Output: true </pre>
Example 3:
<pre>Input: s = "(]" Output: false </pre>
Example 4:
<pre>Input: s = "([)]" Output: false </pre>
Example 5:
<pre>Input: s = "{[]}" Output: true </pre>
Constraints:
1 <= s.length <= 10<sup>4</sup>sconsists of parentheses only'()[]{}'.
</div>
题目大意：
求给定字符串是否合法括号配对。
算法思路：
括号题优先考虑用Stack
注意事项：
- 三种不合法情况： '[' (stack有余), ']' (要匹配的时候stack为空), '{]' (不匹配)
第二遍
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14def isValid(self, s: str) -> bool:
stack = []
paren_dict = {')': '(', '}':'{', ']':'['}
for i in range(len(s)):
if s[i] in '([{':
stack.append(s[i])
elif not stack:
return False
elif stack[-1] != paren_dict[s[i]]:
return False
else:
stack.pop()
return False if stack else True
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17PARENTHESES_DICT = {'(': ')', '[': ']', '{': '}'}
class Solution:
def isValid(self, s: str) -> bool:
if not s:
return False
stack = []
for char in s:
if char in '([{':
stack.append(char)
else:
if not stack:
return False
left = stack.pop()
if PARENTHESES_DICT[left] != char:
return False
return True if not stack else False
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
