301. Remove Invalid Parentheses - jiejackyzhang/leetcode-note GitHub Wiki

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())()"]
")(" -> [""]

解题思路为：

  • 通过计数可以判断valid parenthesis，counter遇'('加1，遇')'减1。
  • 若counter为负，则说明需要删除一个')'，为避免duplicates，如果有连续的')'，我们每次都删第一个。
  • 删除')'后，prefix就是valid的，然后我们可以call the function recursively来处理剩余部分。 这里我们需要记住上一次删除')'的位置，否则若每次从0开始的话，会产生duplicates。
  • 对于诸如'(()(()'的，怎么删除'('呢，一个技巧为将string翻转，然后用同样的方法删除'('。
public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        remove(s, res, 0, 0, new char[]{'(', ')'});
        return res;
    }
    
    private void remove(String s, List<String> res, int iStart, int jStart, char[] par) {
        int stack = 0;
        for(int i = iStart; i < s.length(); i++) {
            if(s.charAt(i) == par[0]) stack++;
            if(s.charAt(i) == par[1]) stack--;
            if(stack >= 0) continue;
            for(int j = jStart; j <= i; j++) {
                if(s.charAt(j) == par[1] && (j == jStart || s.charAt(j-1) != par[1])) {
                    remove(s.substring(0, j) + s.substring(j+1, s.length()), res, i, j, par);
                }
            }
            return; // have tried every possible ways to remove extra par[1], and this is non valid, so return
        }
        // if s is valid in terms of ')', then reverse it to remove extra '('
        // if s is valid in terms of '(', then s is valid, add it to res
        String reversed = new StringBuilder(s).reverse().toString();
        if(par[0] == '(') {
            remove(reversed, res, 0, 0, new char[]{')', '('});
        } else {
            res.add(reversed);
        }
    }
}
⚠️ **GitHub.com Fallback** ⚠️