[Leetcode] 0020. 有效的括号

20. 有效的括号

点击上方，跳转至leetcode

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

1.  
   输入：s = "()"
2.  
   输出：true

示例 2：

1.  
   输入：s = "()[]{}"
2.  
   输出：true

示例 3：

1.  
   输入：s = "(]"
2.  
   输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

解法

方法一：栈

遍历括号字符串 \(s\)，遇到左括号时，压入当前的左括号；遇到右括号时，弹出栈顶元素(若栈为空，直接返回 false)，判断是否匹配，若不匹配，直接返回 false。

也可以选择遇到左括号时，将右括号压入栈中；遇到右括号时，弹出栈顶元素(若栈为空，直接返回 false)，判断是否是相等。若不匹配，直接返回 false。

两者的区别仅限于括号转换时机，一个是在入栈时，一个是在出栈时。

遍历结束，若栈为空，说明括号字符串有效，返回 true；否则，返回 false。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为括号字符串 \(s\) 的长度。

Python3

1.  
   class Solution:
2.  
   def isValid(self, s: str) -> bool:
3.  
   if len(s) % 2 == 1:
4.  
   return False
5.  
    
6.  
   pairs = {
7.  
   ")": "(",
8.  
   "]": "[",
9.  
   "}": "{",
10.  
    }
11.  
    stack = list()
12.  
    for ch in s:
13.  
    if ch in pairs:
14.  
    if not stack or stack[-1] != pairs[ch]:
15.  
    return False
16.  
    stack.pop()
17.  
    else:
18.  
    stack.append(ch)
19.  
     
20.  
    return not stack

C

1.  
   class Solution {
2.  
   public:
3.  
   bool isValid(string s) {
4.  
   int n = s.size();
5.  
   if (n % 2 == 1) {
6.  
   return false;
7.  
   }
8.  
    
9.  
   unordered_map<char, char> pairs = {
10.  
    {')', '('},
11.  
    {']', '['},
12.  
    {'}', '{'}
13.  
    };
14.  
    stack<char> stk;
15.  
    for (char ch: s) {
16.  
    if (pairs.count(ch)) {
17.  
    if (stk.empty() || stk.top() != pairs[ch]) {
18.  
    return false;
19.  
    }
20.  
    stk.pop();
21.  
    }
22.  
    else {
23.  
    stk.push(ch);
24.  
    }
25.  
    }
26.  
    return stk.empty();
27.  
    }
28.  
    };