20.有效的括号

发表于 分类于 阅读次数：

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

有效字符串需满足：

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

解题思路

这是一道经典的栈应用题目。核心思想是：

  • 遇到左括号就入栈
  • 遇到右括号就检查栈顶元素是否匹配
  • 最后检查栈是否为空

方法一：栈解法

时间复杂度 O(n)、空间复杂度 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    // 创建栈
    const stack = [];
    
    // 创建括号映射关系
    const bracketMap = {
        ')': '(',
        '}': '{',
        ']': '['
    };
    
    for (let char of s) {
        // 如果是左括号，直接入栈
        if (char === '(' || char === '{' || char === '[') {
            stack.push(char);
        } else {
            // 如果是右括号，检查栈顶元素是否匹配
            if (stack.length === 0 || stack.pop() !== bracketMap[char]) {
                return false;
            }
        }
    }
    
    // 最后检查栈是否为空
    return stack.length === 0;
};

方法二：优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var isValid = function(s) {
    const stack = [];
    const pairs = {
        '(': ')',
        '{': '}',
        '[': ']'
    };
    
    for (let char of s) {
        if (pairs[char]) {
            // 左括号入栈
            stack.push(char);
        } else {
            // 右括号，检查栈顶
            if (stack.length === 0 || pairs[stack.pop()] !== char) {
                return false;
            }
        }
    }
    
    return stack.length === 0;
};

方法三：使用数组模拟栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var isValid = function(s) {
    const stack = [];
    
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        
        switch (char) {
            case '(':
            case '{':
            case '[':
                stack.push(char);
                break;
            case ')':
                if (stack.pop() !== '(') return false;
                break;
            case '}':
                if (stack.pop() !== '{') return false;
                break;
            case ']':
                if (stack.pop() !== '[') return false;
                break;
        }
    }
    
    return stack.length === 0;
};

解题要点

  1. 栈的应用：这是栈数据结构的经典应用场景
  2. 括号匹配：需要检查左右括号的类型和顺序
  3. 边界情况：
    • 空字符串返回 true
    • 只有左括号或右括号的情况
    • 括号不匹配的情况
  4. 时间复杂度：O(n)，每个字符只遍历一次
  5. 空间复杂度：O(n)，最坏情况下所有字符都是左括号

面试要点

  • 高频考点：这道题是面试中的高频题目，考察栈的应用
  • 代码简洁性：面试中要写出简洁清晰的代码
  • 边界处理：要注意各种边界情况的处理
  • 时间复杂度：能够分析时间复杂度和空间复杂度

相关题目

最后更新: 2025-01-24