301.删除无效的括号

删除无效的括号

给你一个由若干括号和字母组成的字符串 s，删除最小数量的无效括号，使得输入的字符串有效。返回所有可能的结果。

解析

BFS 逐层删除一个括号，找到第一层有效结果即停止。

var removeInvalidParentheses = function (s) {
  function isValid(str) {
    let count = 0;
    for (const ch of str) {
      if (ch === '(') count++;
      else if (ch === ')') count--;
      if (count < 0) return false;
    }
    return count === 0;
  }
  const visited = new Set([s]);
  let queue = [s];
  while (queue.length) {
    const valid = queue.filter(isValid);
    if (valid.length) return valid;
    const next = [];
    for (const str of queue) {
      for (let i = 0; i < str.length; i++) {
        if (str[i] !== '(' && str[i] !== ')') continue;
        const newStr = str.slice(0, i) + str.slice(i + 1);
        if (!visited.has(newStr)) { visited.add(newStr); next.push(newStr); }
      }
    }
    queue = next;
  }
  return [''];
};