有效的括号 - Stellar Observer Protocol

503 字

3 分钟

有效的括号

2025-08-12

Algorithms

栈

/

字符串

题目描述#

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

有效字符串需满足：

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

解题思路#

栈结构应用：
- 遍历字符串，遇左括号（(, [, {）入栈
- 遇右括号（), ], }）检查栈顶元素是否匹配
匹配机制：
- 若栈空或不匹配 → 无效
- 若匹配则弹出栈顶
结果判定：
- 遍历结束后栈空 → 有效
- 栈非空 → 无效
预判优化：
- 字符串长度为奇数直接无效

关键洞察#

后进先出特性：
- 最近左括号需最先匹配（栈完美实现）
- 右括号必须匹配当前栈顶
映射表优化：
- 使用哈希表存储括号对（右→左）
- 快速判断匹配关系
无效状态剪枝：
- 栈空遇右括号立即返回
- 栈非空结束遍历无效
对称性保障：
- 有效串必有偶数字符
- 左括号数 = 右括号数

复杂度分析#

指标	说明
时间复杂度	O(n)：遍历字符串一次，栈操作 O(1)
空间复杂度	O(n)：栈空间（最坏全左括号存储）

代码实现#

1
/**
2
 * @param {string} s
3
 * @return {boolean}
4
 */
5
const isValid = (s) => {
6
    // 奇数长度预判
7
    if (s.length % 2 !== 0) return false;
8

9
    const stack = [];
10
    // 右括号到左括号的映射
11
    const map = {
12
        ')': '(',
13
        ']': '[',
14
        '}': '{'
15
    };
16

17
    for (let char of s) {
18
        if (char === '(' || char === '[' || char === '{') {
19
            stack.push(char); // 左括号入栈
20
        } else {
21
            // 栈空遇右括号 或 栈顶不匹配
22
            if (stack.length === 0 || stack.pop() !== map[char]) {
23
                return false;
24
            }
25
        }
26
    }
27
    return stack.length === 0; // 栈空有效
28
};