> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/1-200/20.-you-xiao-de-kuo-hao.md).

# 20. 有效的括号

<https://leetcode-cn.com/problems/valid-parentheses/>

## 解法一：

用栈，一次扫描输入串，将所有左括号入栈，遇到右括号就与栈顶比对，借助两个字典left和right判断是否成对，成对则弹栈，不成对直接返回False。（注意栈不能为空，否则pop会报错）。遇到右括号且栈为空，说明右括号没有匹配，返回False。

最后判断栈是否为空，为空说明匹配完毕。复杂度O(n)

```python
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        left = {'(':0, '{':1, '[':2}    #左括号字典
        right = {')':0, '}':1, ']':2}   #右括号字典
        for ch in s:
            if ch in left:    #是左括号
                stack.append(ch)
            else:   #是右括号
                if len(stack) > 0 and left[stack[-1]] == right[ch]:
                    stack.pop()
                else:
                    return False
        return len(stack) == 0
```

2020.3.24

```python
class Solution:
    def isValid(self, s: str) -> bool:
        l = '([{'   #左括号集
        r = ')]}'   #右括号集，顺序与左括号一一对应
        stack = []
        for c in s:
            if c in l:
                 stack.append(c)
            else:   #右括号
                if len(stack) > 0:  #栈非空，取出栈顶比较，序号相等则匹配
                    if l.index(stack[-1]) == r.index(c):
                        stack.pop()
                    else:   #匹配不上
                        return False
                else:   #栈空，遇到单独右括号
                    return False
        return len(stack) == 0
```

2024.3.30

```java
class Solution:
    def isValid(self, s: str) -> bool:
        l = '([{'   #左括号集
        r = ')]}'
        stack = []
        for c in s:
            if c in l:
                stack.append(c)
            else:
				# 右括号只有匹配 和 不匹配 两种情况，匹配则弹栈，不匹配直接返回
                if len(stack) > 0 and r.index(c) == l.index(stack[-1]):
                    stack.pop()
                else:
                    return False
        return len(stack) == 0
```