006-有效的括号 (Valid Parentheses)

题目描述

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

有效字符串需满足：

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

示例

输入：s = "()"
输出：true

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

输入：s = "(]"
输出：false

输入：s = "([)]"
输出：false

输入：s = "{[]}"
输出：true

解题思路

使用栈来匹配括号。遍历字符串，遇到左括号就入栈，遇到右括号就检查栈顶元素是否是对应的左括号。如果匹配就弹出栈顶元素，如果不匹配或栈为空就返回false。

JavaScript 解决方案

/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = (s) => {
    const stack = [];
    const bracketMap = {
        ')': '(',
        '}': '{',
        ']': '['
    };
    
    for (const char of s) {
        // 如果是右括号
        if (bracketMap[char]) {
            // 检查栈顶元素是否是对应的左括号
            if (stack.length === 0 || stack.pop() !== bracketMap[char]) {
                return false;
            }
        } else {
            // 如果是左括号，入栈
            stack.push(char);
        }
    }
    
    // 检查栈是否为空
    return stack.length === 0;
};

复杂度分析

时间复杂度：O(n)，其中 n 是字符串长度
空间复杂度：O(n)，最坏情况下栈的大小为 n

测试用例

// 测试函数
const testIsValid = () => {
    const testCases = [
        { s: "()", expected: true },
        { s: "()[]{}", expected: true },
        { s: "(]", expected: false },
        { s: "([)]", expected: false },
        { s: "{[]}", expected: true },
        { s: "(", expected: false },
        { s: ")", expected: false },
        { s: "", expected: true },
        { s: "(((", expected: false },
        { s: ")))", expected: false },
        { s: "({[]})", expected: true },
        { s: "({[}])", expected: false }
    ];

    testCases.forEach((testCase, index) => {
        const result = isValid(testCase.s);
        const passed = result === testCase.expected;
        console.log(`测试用例 ${index + 1}: ${passed ? '通过' : '失败'}`);
        console.log(`输入: s = "${testCase.s}"`);
        console.log(`期望: ${testCase.expected}, 实际: ${result}\n`);
    });
};

// 运行测试
testIsValid();

关键点总结

栈的使用：利用栈的先进后出特性匹配括号
哈希表映射：使用对象存储右括号到左括号的映射
边界处理：空字符串、单个字符的处理
栈空检查：遇到右括号时检查栈是否为空
最终检查：遍历结束后检查栈是否为空

总结

这道题考察了以下重点：

栈的应用：理解栈在括号匹配中的作用
字符串遍历：如何高效地处理字符串
数据结构选择：选择合适的哈希表存储映射关系
边界处理：对各种边界情况的考虑

栈解法是最优解，时间复杂度为 O(n)，空间复杂度为 O(n)。在实际面试中，建议先解释栈的工作原理，然后实现算法。

006-有效的括号 (Valid Parentheses)

On this page