[LeetCode][JavaScript]Remove Invalid Parentheses

Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

https://leetcode.com/problems/remove-invalid-parentheses/

 

 

 

 

---

 

 

 

( 和 )总是成对出现的，出现在 ( 之前的 ) 没有意义。

开变量countLeft记录还没匹配的 ( 的次数。

 

每轮循环三种情况：

1. (， 可以选择拿或不拿;

2. )， 如果有没匹配的 ( ，可以选择拿或不拿，否则只能不拿;

3. 其他字母直接拿。

 

因为要移除最少的括号，开变量maxLeft记录最多有几对括号，即最多出现过几个匹配成功的 (。

注意到这两句话的顺序:

dfs(str.substring(1), subRes + '(', countLeft + 1, maxLeft + 1);
dfs(str.substring(1), subRes, countLeft, maxLeft);

保证了匹配括号多的结果一定会先出现在结果数组中，不会遗漏结果。

https://leetcode.com/discuss/68272/straight-forward-solution-with-explanation

/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function(s) {
    var res = [], max = 0;
    dfs(s, "", 0, 0);
    return res.length !== 0 ? res : [""];

    function dfs(str, subRes, countLeft, maxLeft){
        if(str === ""){
            if(countLeft === 0 && subRes !== ""){
                if(maxLeft > max)
                    max = maxLeft;
                if(max === maxLeft && res.indexOf(subRes) === -1)
                    res.push(subRes);
            }
            return;
        }
        if(str[0] === '('){
            dfs(str.substring(1), subRes + '(', countLeft + 1, maxLeft + 1);
            dfs(str.substring(1), subRes, countLeft, maxLeft);
        }else if(str[0] === ')'){
            if(countLeft > 0)
                dfs(str.substring(1), subRes + ')', countLeft - 1, maxLeft);
            dfs(str.substring(1), subRes, countLeft, maxLeft);
        }else{
            dfs(str.substring(1), subRes + str[0], countLeft, maxLeft);
        }
    }
};