LeetCode 20：有效的括号（暴力法与栈）

题目描述

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

有效字符串需要满足：

1. 左括号必须由相同类型的右括号闭合；
2. 左括号必须按照正确的顺序闭合；
3. 每个右括号都必须有一个与之对应的左括号。

例如：

解法一：暴力消除

不断删除字符串中相邻且匹配的 ()、[] 和 {}：

• 如果最后字符串变为空，说明所有括号都能正确匹配；
• 如果某一轮没有删除任何内容，但字符串仍不为空，说明字符串无效。

以 {[()]} 为例：

{[()]}  ->  {[]}  ->  {}  ->  空字符串

JavaScript 实现：

var isValid = function (s) {
    let previousLength = -1;

    while (s.length !== previousLength) {
        previousLength = s.length;
        s = s
            .replaceAll("()", "")
            .replaceAll("[]", "")
            .replaceAll("{}", "");
    }

    return s.length === 0;
};

每轮替换都需要遍历字符串，最坏情况下还要执行约 n / 2 轮，因此：

• 时间复杂度：O(n²)；
• 空间复杂度：O(n)，因为 JavaScript 字符串不可变，每次替换都会生成新字符串。

这种写法容易理解，但会重复遍历字符串，不适合作为最优解。

解法二：栈

括号匹配具有明显的“后进先出”特点：最后出现的左括号，必须最先被对应的右括号闭合。因此可以用数组模拟栈：

1. 遇到左括号 (、[、{，将它压入栈中；
2. 遇到右括号 )、]、}，检查它是否与栈顶的左括号匹配；
3. 匹配则弹出栈顶元素，否则立即返回 false；
4. 遍历结束后，只有栈为空时才说明全部括号都完成了匹配。

var isValid = function (s) {
    const stack = [];
    const pairs = new Map([
        ["(", ")"],
        ["[", "]"],
        ["{", "}"]
    ]);

    for (const char of s) {
        if (pairs.has(char)) {
            stack.push(char);
            continue;
        }

        if (stack.length === 0) {
            return false;
        }

        const leftBracket = stack.pop();
        if (pairs.get(leftBracket) !== char) {
            return false;
        }
    }

    return stack.length === 0;
};

为什么最后还要判断栈是否为空？

例如输入 ((( 时，遍历过程中不会遇到不匹配的右括号，但仍有三个左括号没有闭合。此时栈不为空，所以结果应该是 false。

复杂度分析

• 时间复杂度：O(n)，每个字符只会入栈或出栈一次；
• 空间复杂度：O(n)，最坏情况下字符串全部由左括号组成。

总结

暴力消除法比较直观，适合理解括号匹配的过程；栈解法只需遍历一次字符串，效率更高，也更符合这道题“后进先出”的结构特征。

如果文章对你有帮助，欢迎点赞；如果发现错误或有其他思路，也欢迎留言交流。

我的个人网站：hongweizhu.com

END