Straight Forward Solution with Explanation


  • 2
    T

    ) is always follow (, so we just need to count the unmatched (.

    Three situations in each turn:

    1. (, pick and not pick it.
    2. ), if we have unmatched (, 2 choices, else drop it.
    3. pick other chars.

    Since it need to remove the minimum brackets, we should figure out the maximum matched ().
    Notice the order of below two lines:

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

    It ensures the maximum result appear before the shorter ones.

    /**
     * @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);
    		}
    	}
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.