题解 | #有效括号序列#

题目链接

有效括号序列

题目描述

给出一个仅包含字符'('、')'、'{'、'}'、'['和']'的字符串，判断给出的字符串是否是合法的括号序列。

合法的括号序列需要满足以下两个条件：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

例如，"()" 和 "()[]{}" 都是合法的，但 "(]" 和 "([)]" 不是。

输入格式 一个字符串 s。

输出格式 如果字符串是有效的括号序列，则输出 "true"，否则输出 "false"。

示例

输入: ([)]
输出: false
输入: {[]}
输出: true

解题思路

这是一个典型的可以使用栈来解决的问题。栈的"后进先出"（LIFO）特性完美地契合了括号匹配的逻辑：最后出现的左括号应该被最先遇到的右括号匹配。

这是一个核心代码（Core Code）模式的题目，意味着我们不需要自己处理输入和输出，只需要在题目预设的类中实现核心的 isValid 函数/方法即可。

算法步骤：

初始化一个空栈。这个栈用来存放所有尚未匹配的左括号。
遍历输入字符串 s 中的每一个字符 c。
根据字符 c 的类型进行判断：
- 如果 c 是一个左括号（(、[、{），说明我们开启了一个新的括号对，将其压入栈中，等待未来的右括号来匹配。
- 如果 c 是一个右括号（)、]、}），说明一个匹配机会来了。
  - 首先检查栈是否为空。如果栈是空的，意味着这个右括号没有对应的左括号，序列必然不合法。直接返回 false。
  - 如果栈不为空，弹出栈顶的元素 top。这个 top 就是最近遇到的、等待匹配的左括号。
  - 检查 top 是否与当前的右括号 c 匹配（例如，( 是否对应 )）。
    - 如果不匹配（例如，top 是 ( 而 c 是 ]），则序列不合法。直接返回 false。
    - 如果匹配，则说明这对括号成功闭合，我们继续遍历下一个字符。
最终检查：当遍历完整个字符串后，检查栈的状态。
- 如果栈是空的，说明所有的左括号都找到了与之匹配的右括号，整个序列是合法的。返回 true。
- 如果栈不为空，说明有多余的左括号没有被匹配（例如 s = "[("），序列不合法。返回 false。

通过这种方式，我们只需对字符串进行一次线性扫描即可完成判断。

代码

cpp
java
python

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool isValid(string s) {
        stack<char> st;
        map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };

        for (char c : s) {
            // 如果字符是右括号
            if (pairs.count(c)) {
                if (st.empty() || st.top() != pairs.at(c)) {
                    return false;
                }
                st.pop();
            } else { // 如果字符是左括号
                st.push(c);
            }
        }

        return st.empty();
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> pairs = new HashMap<>();
        pairs.put(')', '(');
        pairs.put(']', '[');
        pairs.put('}', '{');

        for (char c : s.toCharArray()) {
            if (pairs.containsKey(c)) { // 是右括号
                if (stack.isEmpty() || !stack.pop().equals(pairs.get(c))) {
                    return false;
                }
            } else { // 是左括号
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return bool布尔型
#
class Solution:
    def isValid(self , s ):
        stack = []
        pairs = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        for char in s:
            if char in pairs:  # 是右括号
                if not stack or stack.pop() != pairs[char]:
                    return False
            else:  # 是左括号
                stack.append(char)
                
        return not stack

算法及复杂度

算法: 基于栈的线性扫描。
时间复杂度: $\mathcal{O}(L)$ ，其中 L 是输入字符串的长度。我们只对字符串进行一次遍历。
空间复杂度: $\mathcal{O}(L)$ 。在最坏情况下（例如，字符串全由左括号组成），栈的大小将与输入字符串的长度相同。