判断括号字符串是否有效

问题

给定一个只包含括号字符的字符串，判断该字符串是否有效。有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合
2. 左括号必须以正确的顺序闭合
3. 支持三种括号类型：()、[]、{}

例如：

• "()" → 有效
• "()[]{}" → 有效
• "(]" → 无效
• "([)]" → 无效
• "{[]}" → 有效

解答

/**
 * 判断括号字符串是否有效
 * @param {string} s - 待检测的括号字符串
 * @return {boolean} - 是否有效
 */
function isValidBrackets(s) {
  // 空字符串视为有效
  if (!s) return true;
  
  // 奇数长度的字符串一定无效
  if (s.length % 2 !== 0) return false;
  
  // 括号映射表
  const map = {
    ')': '(',
    ']': '[',
    '}': '{'
  };
  
  // 使用栈存储左括号
  const stack = [];
  
  for (let char of s) {
    // 如果是右括号
    if (map[char]) {
      // 栈为空或栈顶元素不匹配，返回 false
      if (!stack.length || stack[stack.length - 1] !== map[char]) {
        return false;
      }
      // 匹配成功，弹出栈顶元素
      stack.pop();
    } else {
      // 如果是左括号，入栈
      stack.push(char);
    }
  }
  
  // 栈为空说明所有括号都匹配成功
  return stack.length === 0;
}

使用示例

// 测试用例
console.log(isValidBrackets("()"));        // true
console.log(isValidBrackets("()[]{}"));    // true
console.log(isValidBrackets("{[]}"));      // true
console.log(isValidBrackets("(]"));        // false
console.log(isValidBrackets("([)]"));      // false
console.log(isValidBrackets("{[}]"));      // false
console.log(isValidBrackets(""));          // true
console.log(isValidBrackets("(("));        // false
console.log(isValidBrackets("(()())"));    // true
console.log(isValidBrackets("({[]})"));    // true

// 边界情况测试
console.log(isValidBrackets("("));         // false - 单个左括号
console.log(isValidBrackets(")"));         // false - 单个右括号
console.log(isValidBrackets(")("));        // false - 顺序错误

关键点

• 栈数据结构：利用栈的后进先出（LIFO）特性，完美匹配括号的嵌套关系

• 哈希映射：使用对象存储右括号到左括号的映射关系，快速判断括号类型和匹配

• 遍历策略：

  • 遇到左括号 (、[、{ 时入栈
  • 遇到右括号时检查栈顶是否为对应的左括号

• 边界处理：

  • 空字符串返回 true
  • 奇数长度字符串直接返回 false（优化性能）
  • 遍历结束后检查栈是否为空

• 时间复杂度：O(n)，需要遍历字符串一次

• 空间复杂度：O(n)，最坏情况下所有字符都是左括号需要入栈