52.有效的括号

题目

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

有效字符串需满足:

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

示例 1:

• 输入：s = "()"

• 输出：true

示例 2:

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

• 输出：true

示例 3:

• 输入：s = "(]"

• 输出：false

示例 4:

• 输入：s = "([])"

• 输出：true

提示:

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

思路

要求是“以正确的顺序闭合”，所以([)]这种是错误的。

要判断一个仅包含括号字符()[]{}的字符串是否有效（即括号是否按正确顺序闭合），可通过栈Stack这一数据结构高效解决。

括号的闭合需满足“后进先出” 的嵌套关系: 最后出现的左括号需优先匹配右括号，栈的LIFO后进先出特性完美契合此需求。

• 遍历字符: 逐个处理字符串中的字符。
• 左括号入栈: 遇到(, {, [时压入栈。

• 右括号匹配: 遇到), }, ]时:

  • 若栈为空 → 无效（右括号多余）。
  • 若栈顶左括号与当前右括号不匹配 → 无效。
  • 匹配则弹出栈顶元素。

• 最终校验: 遍历结束后栈必须为空（左括号全被匹配）。

使用ArrayDeque替代传统Stack类，因前者在push/pop操作上效率更高（无同步开销）。

import java.util.ArrayDeque;
import java.util.Deque;
public class Solution {
    public boolean isValid(String s) {
        // 边界处理：空字符串有效，null 或奇数长度直接无效
        if (s == null) {
            return false;
        }
        if (s.isEmpty()) {
            return true;
        }
        if (s.length() % 2 != 0) {
            // 奇数长度不可能完全匹配
            return false;
        }

        // 使用双端队列模拟栈（高效）
        Deque<Character> stack = new ArrayDeque<>(); 

        for (char c : s.toCharArray()) {
            // 左括号：入栈
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } 
            // 右括号：检查匹配
            else {
                if (stack.isEmpty()) return false; // 栈空说明右括号多余
                char top = stack.pop(); // 弹出栈顶左括号
                // 检查括号类型是否匹配
                if ((c == ')' && top != '(') || 
                    (c == '}' && top != '{') || 
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty(); // 栈空说明所有左括号均被匹配
    }
}

# 映射表优化：用字典 bracket_map 存储括号对应关系，避免冗长的 if-else 分支
def isValid(s: str) -> bool:
    stack = []
    bracket_map = {')': '(', ']': '[', '}': '{'}  # 右括号到左括号的映射
    for char in s:
        if char in bracket_map.values():  # 左括号入栈
            stack.append(char)
        elif char in bracket_map:  # 右括号匹配
            if not stack or stack.pop() != bracket_map[char]:
                return False
    return not stack

class Solution {
    fun isValid(s: String): Boolean {
        val stack = ArrayDeque<Char>()

        for (c in s) {
            when (c) {
                '(', '{', '[' -> stack.addLast(c)
                ')' -> if (stack.isEmpty() || stack.removeLast() != '(') {
                    return false
                }
                '}' -> if (stack.isEmpty() || stack.removeLast() != '{') {
                    return false
                }
                ']' -> if (stack.isEmpty() || stack.removeLast() != '[') {
                    return false
                }
            }
        }

        return stack.isEmpty()
    }
}

复杂度分析:

• 时间复杂度: O(N)
• 空间复杂度: O(N)

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!