开发者LT的博客
0%

力扣20题-有效的括号-题解

发表于 分类于
本文字数： 2.8k 阅读时长 ≈ 3 分钟
栈的经典应用

力扣20题-有效的括号-题解

题目描述

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

有效字符串需满足：

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示

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

接口

1
2
3
4
5
6
class Solution {
public:
    bool isValid(string s) {
        
    }
};

分析

以 "([])"为例：

1
2
3
读 '('  → 左括号。它有没有对应的右括号，现在还不知道，先存着
读 '['  → 又是左括号，同样先存着
读 ']'  → 右括号来了，它该跟谁配？

] 要配的是紧挨着它左边的 [，也就是最后存进去的那个左括号，不是更早存进去的 (。配完这一对，接着读到一个 )，它跟剩下那个还没被配掉的 ( 配。

走完这一遍，能看出”存括号”这件事有两个要求：

存和取都只在最后进来的那个元素上进行。 存左括号往末尾加，取左括号从末尾拿。最早存进去的 ( 一直被压在下面，直到 [ 被取走了才轮到它。

后存进去的先被取走。 [ 比 ( 后存，但 ] 比 ) 先出现，所以 [ 先被取走。

这两条要求，正好对上栈的两条特性：

这个过程的要求 栈的特性
存和取都只在最后进来的元素上 只允许在栈顶一端插入和删除
后存进去的先被取走 后进先出

栈顶就是”最后存进去的那个”，存是入栈，取是出栈。用栈把 "([])" 重走一遍：

1
2
3
4
5
读 '('  → 左括号，入栈                              栈：( 
读 '['  → 左括号，入栈                              栈：( [
读 ']'  → 右括号，跟栈顶 '[' 比，同类型，出栈          栈：( 
读 ')'  → 右括号，跟栈顶 '(' 比，同类型，出栈          栈：（空）
扫描结束，栈为空 → 返回 true

顺序不对的情况，栈也能抓出来。以 "([)]" 为例：

1
2
3
读 '('  → 入栈                              栈：( 
读 '['  → 入栈                              栈：( [
读 ')'  → 跟最后入栈的 '[' 比，不是同一类型 → 返回 false

) 想配的是 (，但 ( 被 [ 压在下面，栈顶露出来的是 [。取不到想要的那个。

抽象成算法：

  1. 遍历字符串
  2. 遇到左括号，直接入栈。因为等要匹配的时候，最后遇到的那个左括号一定在栈顶，取出来就能用
  3. 遇到右括号，从栈顶取出一个左括号比较
    • 同类型，匹配成功，继续遍历下一个字符
    • 不同类型，匹配失败，算法直接结束
  4. 遍历结束后，栈应该是空的。不空说明有左括号没等到右括号

第 4 步容易漏。左括号比右括号多的时候，整个遍历过程一次都不会失败，错误要等到收尾才暴露。

一共有三种情况会让字符串无效：

情况 例子 在哪一步被发现
右括号多了 "]" 遇到右括号时栈是空的，没有左括号能跟它配
类型对不上 "(]" 弹出的栈顶和当前右括号不是一对
左括号多了 "(" 扫描结束栈里还有元素，说明有左括号没被闭合

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool isValid(string s) {
        stack<char> cs;
        for (char ch : s)
        {
            //遇到左括号
            if (ch == '(' || ch == '[' || ch == '{')
            {
                cs.push(ch);        // 左括号一律先入栈，等着后面被匹配
            }
            //遇到右括号
            else                    
            {
                // 栈空说明还没有左括号，右括号就先来了，直接错误
                if (cs.empty())
                {
                    return false;
                }
                char c = cs.top();  // 取出栈顶，也就是最近的未匹配左括号
                cs.pop();
                // 栈顶和当前右括号必须是同一对，如果不是一对，则错误
                if ((c == '(' && ch != ')') || (c == '[' && ch != ']') || (c == '{' && ch != '}'))
                {
                    return false;
                }
            }
        }
        // 全部匹配完栈应该是空的，如果不是空栈，说明左括号多了
        return cs.empty();
    }
};

逐段说明：

stack<char> cs; 存的是还没被匹配的左括号。

遍历用范围 for，char ch : s 依次拿到每个字符。

第一个分支处理左括号，三种左括号都 push 进去。这里不需要做判断，左括号本身没有合不合法的问题，它合不合法取决于后面有没有配对的右括号。

else 分支处理右括号，先判空。栈空说明前面没有任何待匹配的左括号，当前这个右括号没有归属，直接返回 false。

cs.top() 拿到栈顶，紧接着 cs.pop() 把它弹掉。

接下来比较类型。三个条件用 || 连起来，任意一个成立就说明不匹配。以 c == '(' && ch != ')' 为例：栈顶是左圆括号，但当前字符不是右圆括号，那这一对就不成立。

循环结束后 return cs.empty();。扫描完栈里还有剩余，说明有左括号始终没等到它的右括号。

复杂度

  • 时间：每个字符进栈或出栈一次，都是 O(1)，总共 O(n)
  • 空间：最坏情况全是左括号，栈里存 n 个字符，O(n)

几个容易报错的地方

空栈时取栈顶。 top() 和 pop() 都要求栈非空，对空栈调用是未定义行为，不是抛异常。所以判空要放在取栈顶之前。

最后直接 return true。 只判了”有没有中途失败”，漏掉”左括号多出来”这种收尾情况，"("、"([]" 这类输入会被漏判成 true。