题解 | 有效括号序列

1、解题思路

1. 栈的应用： 遍历字符串，遇到左括号 '(', '{', '[' 时，压入栈。遇到右括号 ')' , '}' , ']' 时，检查栈顶是否为对应的左括号： 如果是，弹出栈顶。如果不是，返回 false。遍历结束后，如果栈为空，返回 true；否则返回 false。
2. 边界条件： 空字符串视为合法。字符串长度为奇数时可直接返回 false。

2、代码实现

C++

#include <stack>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    bool isValid(string s) {
        stack<char> st;
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (st.empty() || (c == ')' && st.top() != '(') || (c == ']' &&
                        st.top() != '[') || (c == '}' && st.top() != '{')) {
                    return false;
                }
                st.pop();
            }
        }
        return st.empty();
    }
};

#include <unordered_map>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    bool isValid(string s) {
        // write code here
        if (s.empty()) {
            return true;
        }
        if (s.size() % 2 != 0) {
            return false;   // 奇数长度直接返回 false
        }

        stack<char> st;
        unordered_map<char, char> pairs = {
            {')', '('},
            {'}', '{'},
            {']', '['}
        };

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

        return st.empty();
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        if (s.isEmpty()) return true;
        if (s.length() % 2 != 0) return false;

        Stack<Character> stack = new Stack<>();
        HashMap<Character, Character> pairs = new HashMap<>();
        pairs.put(')', '(');
        pairs.put('}', '{');
        pairs.put(']', '[');

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

        return stack.isEmpty();
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return bool布尔型
#
class Solution:
    def isValid(self , s: str) -> bool:
        # write code here
        if not s:
            return True
        if len(s) % 2 != 0:
            return False

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

        for c in s:
            if c in pairs:  # 当前字符是右括号
                if not stack or stack[-1] != pairs[c]:
                    return False
                stack.pop()
            else:  # 当前字符是左括号
                stack.append(c)

        return not stack

3、复杂度分析

1. 时间复杂度：O(n)，遍历字符串一次。
2. 空间复杂度：O(n)，栈的最大深度为 n/2。