DFS

Explanation: ​ We all know how to check a string of parentheses is valid using a stack. Or even simpler use a counter. The counter will increase when it is ‘(‘ and decrease when it is ‘)’. Whenever the counter is negative, we have more ‘)’ than ‘(‘ in the prefix.

​ To make the prefix valid, we need to remove a ‘)’. The problem is: which one? The answer is any one in the prefix. However, if we remove any one, we will generate duplicate results, for example: s = ()), we can remove s[1] or s[2] but the result is the same (). Thus, we restrict ourself to remove the first ) in a series of concecutive )s.

​ After the removal, the prefix is then valid. We then call the function recursively to solve the rest of the string. However, we need to keep another information: the last removal position. If we do not have this position, we will generate duplicate by removing two ‘)’ in two steps only with a different order. For this, we keep tracking the last removal position and only remove ‘)’ after that.

​ Now one may ask. What about ‘(‘? What if s = ‘(()(()’ in which we need remove ‘(‘? The answer is: do the same from right to left. However a cleverer idea is: reverse the string and reuse the code! Here is the final implement in Java.

const removeInvalidParentheses = function(s) {
  const res = [];
  remove(s, res, 0, 0, "()");
  return res;
};

const remove = function(s, res, last_i, last_j, str) {
  for (let stack = 0, i = last_i, slen = s.length; i < slen; ++i) {
    if (s[i] === str[0]) {
      ++stack;
    }
    if (s[i] === str[1]) {
      --stack;
    }
    if (stack >= 0) {
      continue;
    }
    for (let j = last_j; j <= i; ++j) {
      if (s[j] === str[1] && (j === last_j || s[j - 1] !== str[1])) {
        // 去掉 s[j]
        remove(s.substring(0, j) + s.substring(j + 1, slen), res, i, j, str);
      }
    }
    return;
  }
  const reversedS = s.split('').reverse().join('');
  if (str[0] === '(') {
    remove(reversedS, res, 0, 0, ')(');
  } else {
    res.push(reversedS);
  }
};

BFS

const removeInvalidParentheses = function(s) {
  const res = [],
    queue = [],
    visited = [];
  let found = false;
  queue.push(s);
  visited.push(s);
  while (queue.length !== 0) {
    s = queue.shift();
    if (isValid(s)) {
      console.log(s);
      res.push(s);
      found = true;
    }
    if (found) {
      continue;
    }
    for (let i = 0, ii = s.length; i < ii; ++i) {
      // we only try to remove left or right paren
      if (s[i] !== '(' && s[i] !== ')') continue;
    
      let t = s.substring(0, i) + s.substring(i + 1);
    
      if (!visited.includes(t)) {
        // for each state, if it's not visited, push it to the queue
        queue.push(t);
        visited.push(t);
      }
    }
  }
  return res;
};
const isValid = function(s) {
  let count = 0;
  for (let i = 0, ii = s.length; i < ii; ++i) {
    if (s[i] === "(") {
      ++count;
    }
    // 如果 s[i] === ")" && count === 0 返回 false
    if (s[i] === ")" && count-- === 0) {
      return false;
    }
  }
  return count === 0;
};

BFS解这个问题很不合适,时间复杂度太高了.