[LeetCode 301] Remove Invalid Pa

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 ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

Solution

1. 首先算出最少需要移除的 左右括号的个数
2. Recursively: Try all possible ways to remove right and left parentheses to make the String valid
   • 需要先删除右括号。比如") ()()"，如果先删左括号，那么第一个右括号的存在无论如何都会使表达式无效
   • 每次遇到括号，先删右括号： 判断是否还有需要删除的，然后递归时，从当前删除括号的index处开始
   • 然后再删左括号
   • 如果 左右括号都没有还需要被删除的，就返回表达式

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList<> ();
        // if (s == null || s.length () == 0) {
        //     return result;
        // }
        
        //1. compute the minimun count of left paren and right paren need to be removed 
        int leftRemoveCount = 0;
        int rightRemoveCount = 0;
        
        for (char ch : s.toCharArray ()) {
            if (ch == '(') {
                leftRemoveCount ++;
            }
            
            if (ch == ')') {
                if (leftRemoveCount == 0) {
                    rightRemoveCount ++;
                } else {
                    leftRemoveCount --;
                }
            }
        }
        
        System.out.println (leftRemoveCount + " " + rightRemoveCount);
        if (leftRemoveCount == 0 && rightRemoveCount == 0) {
            result.add (s);
            return result;
        }
        
        //2. Recursively get all possibilities
        removeInvalidParenthesesHelper (s, 0, leftRemoveCount, rightRemoveCount, result);
        
        return result;
    }
    
    public void removeInvalidParenthesesHelper (String str, int start, int leftRemoveCount, int rightRemoveCount, List<String> result) {
        if (leftRemoveCount == 0 && rightRemoveCount == 0) {
            if (isValid (str))
                result.add (str);
            return;
        }
        
        for (int index = start; index < str.length (); index ++) {
            if (index != 0 && str.charAt (index - 1) == str.charAt (index)) {
                continue;
            }
            
            char currentCh = str.charAt (index);
            if (currentCh == ')' && rightRemoveCount > 0) {
                String removedStr = str.substring (0, index) + str.substring (index + 1, str.length ());
                removeInvalidParenthesesHelper (removedStr, index, leftRemoveCount, rightRemoveCount - 1, result);
            } else if (currentCh == '(' && leftRemoveCount > 0) {
                String removedStr = str.substring (0, index) + str.substring (index + 1, str.length ());
                removeInvalidParenthesesHelper (removedStr, index, leftRemoveCount - 1, rightRemoveCount, result);
            }
        }
    }
    
    public boolean isValid (String str) {
        if (str == null || str.length () == 0)
            return true;
        
        int count = 0;
        for (char ch : str.toCharArray ()) {
            if (ch == '(')
                count ++;
            else if (ch == ')')
                count --;
            
            if (count < 0)
                return false;
        }
        
        return count == 0;
    }
}