有效的括号

解题思路

判断一个包含括号的字符串是否有效，可以使用栈来解决这个问题。这个问题可以通过以下步骤来实现：

1. 遇到左括号时，将其推入栈中。
2. 遇到右括号时，检查栈顶的左括号是否与之匹配。如果匹配则将栈顶元素弹出，否则字符串无效。
3. 最后检查栈是否为空，如果栈为空则字符串有效，否则字符串无效。

解法步骤：

1. 创建一个栈来保存左括号。
2. 遍历字符串中的每个字符：
   • 如果是左括号，将其推入栈中。
   • 如果是右括号，检查栈是否为空或者栈顶元素是否与当前右括号匹配：
     • 如果匹配，则弹出栈顶元素。
     • 如果不匹配或栈为空，字符串无效。
3. 遍历结束后，如果栈为空，则字符串有效；否则字符串无效。

JavaScript 实现：

function isValid(s) {
    const stack = [];
    const map = {
        '(': ')',
        '{': '}',
        '[': ']'
    };

    for (let char of s) {
        if (map[char]) {
            // If the character is a left bracket
            stack.push(char);
        } else {
            // If the character is a right bracket
            const topElement = stack.pop();
            if (map[topElement] !== char) {
                return false;
            }
        }
    }

    return stack.length === 0;
}

// 示例
console.log(isValid("()"));       // true
console.log(isValid("()[]{}"));   // true
console.log(isValid("(]"));       // false
console.log(isValid("([)]"));     // false
console.log(isValid("{[]}"));     // true

详细解答过程：

1. 初始化一个空栈 stack 和一个括号匹配的映射 map。
2. 遍历字符串 s 中的每个字符 char：
   • 如果 char 是左括号（即存在于 map 的键中），则将其推入栈 stack。
   • 如果 char 是右括号：
     • 从栈 stack 中弹出栈顶元素 topElement。
     • 检查 map 中 topElement 对应的值是否等于 char。如果不等，则返回 false。
3. 遍历完成后，检查栈 stack 是否为空。如果为空，则返回 true；否则返回 false。

优缺点分析：

优点：

• 时间复杂度为 O(n)，其中 n 是字符串的长度。每个字符只遍历一次。
• 空间复杂度为 O(n)，在最坏情况下（所有字符都是左括号），栈的大小为 n。

缺点：

• 使用了额外的栈空间。