跳到主要内容

有效的括号

问题​

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

有效字符串需满足：

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

示例：

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

来源：LeetCode 20. 有效的括号

答案​

方法一：栈（推荐）​

核心思路：遇到左括号就压栈，遇到右括号就弹出栈顶元素检查是否匹配。

validParentheses.ts
function isValid(s: string): boolean {
  // 奇数长度一定无效
  if (s.length % 2 !== 0) return false;

  const stack: string[] = [];
  const map: Record<string, string> = {
    ')': '(',
    ']': '[',
    '}': '{',
  };

  for (const char of s) {
    if (char === '(' || char === '[' || char === '{') {
      // 左括号：压入栈
      stack.push(char);
    } else {
      // 右括号：检查栈顶是否匹配
      if (stack.length === 0 || stack[stack.length - 1] !== map[char]) {
        return false;
      }
      stack.pop();
    }
  }

  // 栈为空说明所有括号都正确匹配
  return stack.length === 0;
}

执行过程演示：

输入：s = "{[]}"

第1步: char = '{' → 左括号，压栈 → stack = ['{']
第2步: char = '[' → 左括号，压栈 → stack = ['{', '[']
第3步: char = ']' → 右括号，栈顶 '[' === map[']']，匹配！弹出 → stack = ['{']
第4步: char = '}' → 右括号，栈顶 '{' === map['}']，匹配！弹出 → stack = []

最终：stack 为空 → 返回 true
输入：s = "([)]"

第1步: char = '(' → 压栈 → stack = ['(']
第2步: char = '[' → 压栈 → stack = ['(', '[']
第3步: char = ')' → 栈顶 '[' !== map[')'] = '('，不匹配！ → 返回 false
复杂度分析
  • 时间复杂度：O(n)O(n) — 遍历一次字符串
  • 空间复杂度：O(n)O(n) — 最坏情况全是左括号

方法二：使用 Map 替代对象​

使用 Map 更加类型安全，且支持任意类型的键：

validParenthesesMap.ts
function isValid(s: string): boolean {
  if (s.length % 2 !== 0) return false;

  const stack: string[] = [];
  const pairs = new Map<string, string>([
    [')', '('],
    [']', '['],
    ['}', '{'],
  ]);

  for (const char of s) {
    if (pairs.has(char)) {
      // 右括号：检查匹配
      if (stack.pop() !== pairs.get(char)) {
        return false;
      }
    } else {
      // 左括号：压栈
      stack.push(char);
    }
  }

  return stack.length === 0;
}
与方法一的区别

这种写法更简洁，stack.pop() 在栈为空时返回 undefined，自然不等于任何括号，无需单独判断空栈。

方法三：替换消除法（不推荐，仅了解）​

反复替换匹配的括号对为空字符串，直到无法替换：

validParenthesesReplace.ts
function isValid(s: string): boolean {
  let prev = '';
  while (s !== prev) {
    prev = s;
    s = s.replace('()', '').replace('[]', '').replace('{}', '');
  }
  return s.length === 0;
}
不推荐
  • 时间复杂度：O(n2)O(n^2) — 每次替换都要扫描整个字符串
  • 空间复杂度：O(n)O(n) — 字符串替换产生新字符串
  • 面试中使用此方法会被认为不够优秀，但可作为"你还能想到其他方法吗？"的补充回答

常见面试追问​

Q1: 如果只有一种括号 ()，如何简化？​

答案：只需用一个计数器，遇到 ( 加 1，遇到 ) 减 1，过程中计数器不能为负，最终为 0 即有效：

function isValidSimple(s: string): boolean {
  let count = 0;
  for (const char of s) {
    if (char === '(') count++;
    else if (char === ')') count--;
    if (count < 0) return false; // 右括号多了
  }
  return count === 0;
}

Q2: 这道题的实际应用场景是什么？​

答案：

  • 代码编辑器：实时检测括号是否匹配（VS Code、WebStorm）
  • 编译器前端：词法/语法分析中的括号匹配
  • HTML 标签匹配：检测标签是否正确嵌套
  • 数学表达式校验：检测公式中的括号是否合法

Q3: 如何找到第一个不匹配的括号位置？​

答案：

function findFirstInvalid(s: string): number {
  const stack: number[] = []; // 存储索引
  const pairs = new Map([[')', '('], [']', '['], ['}', '{']]);

  for (let i = 0; i < s.length; i++) {
    if (pairs.has(s[i])) {
      if (stack.length === 0 || s[stack[stack.length - 1]] !== pairs.get(s[i])) {
        return i; // 右括号不匹配
      }
      stack.pop();
    } else {
      stack.push(i);
    }
  }

  return stack.length > 0 ? stack[0] : -1; // -1 表示全部匹配
}

相关链接​