20. 有效的括号

力扣题目链接 (opens new window)

题目描述

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

有效字符串需满足：

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

思路

括号匹配为什么会想到用栈？

以 {[]} 为例，最先出现的左括号 {，反而最后才闭合；最后出现的左括号 [，需要最先闭合。这正是后进先出的顺序，所以栈非常适合处理这类对称匹配问题。

写代码之前，先把括号不匹配的情况想清楚。一共有三种：

1. 字符串遍历完了，栈里还有元素，说明左括号多余
2. 当前右括号和栈顶期待的括号不同，说明括号类型不匹配
3. 遇到右括号时栈已经空了，说明右括号多余

代码只要覆盖这三种情况，就不会越写越乱。

那么栈里应该存什么？

常见写法是把左括号入栈，遇到右括号时再判断它们是否配对。但还可以更直接一点：

• 遇到 (，把期待出现的 ) 入栈
• 遇到 [，把期待出现的 ] 入栈
• 遇到 {，把期待出现的 } 入栈
• 遇到右括号，只需要判断它是否等于栈顶元素

左括号出现时，直接把与它匹配的右括号入栈，后面的判断就统一成了“当前字符是否等于栈顶”。

另外，如果字符串长度是奇数，括号一定无法两两配对，可以直接返回 false。

模拟过程

先看三种不匹配的情况。

第一种：字符串已经遍历完，但栈不为空，说明有左括号没有被匹配。

第二种：栈不为空，但当前右括号与栈顶期待的括号不同，说明类型不匹配。

第三种：遇到右括号时栈已经为空，说明它前面没有对应的左括号。

再以 s = "{[]}" 为例：

1. 遇到 {，将期待的 } 入栈
2. 遇到 [，将期待的 ] 入栈，此时栈顶是 ]
3. 遇到 ]，与栈顶相同，弹出 ]
4. 遇到 }，与栈顶相同，弹出 }
5. 字符串遍历结束，栈为空，所以括号有效

完整过程如下：

这里最关键的判断顺序是：先判断栈是否为空，再访问栈顶。否则在右括号多余时直接读取栈顶，会产生非法访问。

解题代码

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 == 1) return false; // 奇数个括号无法两两匹配

        stack<char> st;
        for (char ch : s) {
            // 左括号出现时，保存后面期待遇到的右括号
            if (ch == '(') {
                st.push(')');
            } else if (ch == '[') {
                st.push(']');
            } else if (ch == '{') {
                st.push('}');
            } else {
                // 栈空表示右括号多余；不相等表示括号类型不匹配
                if (st.empty() || st.top() != ch) return false;
                st.pop();
            }
        }

        // 栈不为空，说明还有左括号没有闭合
        return st.empty();
    }
};

复杂度分析

时间复杂度：O(n)，每个字符只会入栈或出栈一次。

空间复杂度：O(n)，最坏情况下所有字符都是左括号，都需要入栈。

其他语言

Python3

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False

        stack = []
        pairs = {'(': ')', '[': ']', '{': '}'}

        for ch in s:
            if ch in pairs:
                stack.append(pairs[ch])
            elif not stack or stack[-1] != ch:
                return False
            else:
                stack.pop()

        return not stack

Java

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 == 1) return false;

        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                stack.push(')');
            } else if (ch == '[') {
                stack.push(']');
            } else if (ch == '{') {
                stack.push('}');
            } else {
                if (stack.isEmpty() || stack.peek() != ch) return false;
                stack.pop();
            }
        }

        return stack.isEmpty();
    }
}

Go

func isValid(s string) bool {
    if len(s)%2 == 1 {
        return false
    }

    stack := make([]byte, 0)
    for i := 0; i < len(s); i++ {
        switch s[i] {
        case '(':
            stack = append(stack, ')')
        case '[':
            stack = append(stack, ']')
        case '{':
            stack = append(stack, '}')
        default:
            if len(stack) == 0 || stack[len(stack)-1] != s[i] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }

    return len(stack) == 0
}

JS

var isValid = function(s) {
    if (s.length % 2 === 1) return false;

    const stack = [];
    const pairs = {
        '(': ')',
        '[': ']',
        '{': '}'
    };

    for (const ch of s) {
        if (ch in pairs) {
            stack.push(pairs[ch]);
        } else if (stack.length === 0 || stack[stack.length - 1] !== ch) {
            return false;
        } else {
            stack.pop();
        }
    }

    return stack.length === 0;
};

与代码随想录联系

这道题是代码随想录栈与队列章节中最经典的栈应用：用栈的后进先出解决成对元素的顺序匹配问题。

完整讲解可以继续阅读代码随想录的20. 有效的括号。掌握本题后，建议录友们继续练习1047. 删除字符串中的所有相邻重复项和150. 逆波兰表达式求值，体会栈在字符串消除和表达式求值中的应用。