有效的括号

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，我们需要判断这个字符串是否有效。一个有效的字符串必须满足两个基本条件：首先，每一个左括号都必须有一个相同类型的右括号与之对应并闭合；其次，括号的闭合顺序必须是正确的，也就是说，最后开启的括号必须最先被闭合。这就像是在编写代码时，我们必须保证每一个函数、对象或数组的定义都能正确地“对齐”，否则代码逻辑就会混乱。

思路分析

处理括号匹配问题最直观的工具就是“栈”这一数据结构。由于括号具有天然的嵌套属性，最近开启的左括号往往是接下来最需要被闭合的。当我们遍历字符串时，每遇到一个左括号，就把它存入栈中，代表这是一个“待解决”的承诺；而每当遇到一个右括号，我们就去查看栈顶最靠近的那条承诺，看它们是否类型一致。如果类型匹配，则将栈顶元素弹出，标志着这一对括号成功“销结”。如果遍历结束时，所有的承诺都已兑现，即栈恢复为空，那么这个字符串就是有效的。

除了使用栈的方案，还有一种非常形象的方法叫做“扫描替换法”。想象一下，如果一个字符串是有效的，它内部一定至少存在一对紧密相邻的完整括号，例如 ()、[] 或 {}。我们可以像消除类游戏一样，不断在字符串中寻找这些成对的最小单元并将其删除。删除后，原本被隔开的括号可能会缩进并形成新的匹配对，我们继续重复这个过程。如果在某一步我们再也找不到可以消除的对子，而字符串依然不为空，那么它就是无效的。

解法

/**
 * 判断给定字符串中的括号是否有效。
 * 有效的标准是：
 * 1. 左括号必须用相同类型的右括号闭合。
 * 2. 左括号必须以正确的顺序闭合。
 * 
 * @param {string} str - 包含 '(', ')', '{', '}', '[', ']' 的字符串
 * @returns {boolean} - 如果字符串有效返回 true，否则返回 false
 */
export function isValidBrackets(str) {
  // 1. 基础校验：如果是空字符串、非字符串或长度为奇数（括号必定无法配对），则直接返回 false
  if (!str || typeof str !== 'string' || str.length % 2 !== 0) {
    return false;
  }

  // 2. 创建一个栈（Stack），利用“后进先出”的特点来处理匹配关系
  const stack = [];
  
  // 3. 定义括号映射关系，键为左括号，值为对应的右括号
  const hashMap = {
    '(': ')',
    '[': ']',
    '{': '}',
  };

  // 4. 遍历字符串中的每一个字符
  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    
    // 如果是左括号（即 char 能在 hashMap 中找到对应的值）
    if (hashMap[char]) {
      // 将对应的“预期右括号”入栈，这样后面遇到右括号时直接对比即可
      stack.push(hashMap[char]);
    } else {
      // 5. 如果是右括号，则从栈顶弹出一个元素进行匹配
      // 如果弹出的元素与当前字符不匹配，说明括号顺序错误或无法配对
      if (stack.pop() !== char) {
        return false;
      }
    }
  }

  // 6. 最后检查栈是否已经清空。如果是空栈，说明所有括号都成功匹配了
  return stack.length === 0;
}
// test case
// 示例 1：
console.log(isValidBrackets('()')); // true

// 示例 2：
console.log(isValidBrackets('()[]{}')); // true

// 示例 3：
console.log(isValidBrackets('(]')); // false

// 示例 4：
console.log(isValidBrackets('([])')); // true

// 示例 5：
console.log(isValidBrackets('([)]')); // false

#有效的括号

#题目描述

#思路分析

#解法

有效的括号

题目描述

思路分析

解法