BFE.devAI解答 - JavaScript 代码题
102. 验证括号字符串

一种解法是使用栈（stack）数据结构来处理括号匹配。遍历字符串，如果当前字符是左括号，就将其压入栈中；如果是右括号，就将栈顶元素弹出，检查是否与当前右括号匹配。如果配对成功，继续遍历；如果失败，说明括号顺序不对或者不配对，直接返回 false。

时间复杂度为 O(n)，其中 n 是字符串的长度，因为每个字符只需要遍历一遍。空间复杂度也是 O(n)，因为需要使用一个栈来保存左括号。

代码示例：

function validate(str) {
  const stack = [];
  const bracketsMap = {
    '(': ')',
    '[': ']',
    '{': '}',
  };
  for (let s of str) {
    if (s in bracketsMap) {
      stack.push(s); // 左括号入栈
    } else {
      const left = stack.pop(); // 栈顶元素出栈
      if (!left || bracketsMap[left] !== s) { // 括号配对失败
        return false;
      }
    }
  }
  return stack.length === 0; // 栈为空说明所有左括号都匹配了
}

可以看到，在配对失败后直接返回 false，避免了继续遍历的开销，最坏情况下空间复杂度是 O(n/2)。代码中使用了 ES6 中的 for...of 语法，以及关系运算符 in 来判断是否为左括号。

还有一种使用正则表达式匹配的解法，不过时间复杂度较高。可以参考下面的代码，它先将字符串中所有括号匹配的部分用空字符串替换，直到不能再匹配为止。如果最终字符串为空，说明所有括号都配对成功，否则说明有未配对的括号。

function validate(str) {
  const reg = /\(\)|\[\]|\{\}/;
  while (str.match(reg)) {
    str = str.replace(reg, '');
  }
  return str.length === 0;
}

这种方法的时间复杂度最坏情况下是 O(n^2)，因为每次用正则表达式替换都需要遍历一遍字符串。空间复杂度是 O(n)，因为需要复制新的字符串进行替换。不过这种解法写起来简单，而且对于简单的字符串可以快速判断。