Description
Remove Invalid Parentheses
HardGiven a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.
Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.
Example 1:
Input: s = "()())()" Output: ["(())()","()()()"]
Example 2:
Input: s = "(a)())()" Output: ["(a())()","(a)()()"]
Example 3:
Input: s = ")("
Output: [""]
Constraints:
1 <= s.length <= 25sconsists of lowercase English letters and parentheses'('and')'.- There will be at most
20parentheses ins.
Solutions
Applied memoization for better performance.
Language: javascript()DONE
CPU Performance58.02%
x
Memory Performance32.70%
x
/**
* @param {string} s
* @return {string[]}
*/
var removeInvalidParentheses = function (s) {
const res = new Set();
const memo = new Set();
const generate = (index, op, cl, str) => {
if (index === s.length) {
if (op === 0 && cl === 0) {
const { open, closed } = count(str);
if (open + closed === 0) {
res.add(str);
}
}
return;
}
const key = index + ':' + op + ':' + cl + ':' + str;
if (memo.has(key)) return;
memo.add(key);
if (s[index] === '(' && op > 0) {
generate(index + 1, op - 1, cl, str);
}
if (s[index] === ')' && cl > 0) {
generate(index + 1, op, cl - 1, str);
}
generate(index + 1, op, cl, str + s[index]);
};
const { open, closed } = count(s);
generate(0, open, closed, '');
return [...res];
};
const count = (str) => {
let open = 0;
let closed = 0;
for (const char of str) {
if (char === '(') {
open++;
} else if (char === ')') {
if (open > 0) {
open--;
} else {
closed++;
}
}
}
return { open, closed };
};