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解这个问题很不合适,时间复杂度太高了.