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

现在有一个字符串包含一些左右括号以及字母。一个合法的字符串是指左括号和右括号必定成对出现。要求得出用最少次数的删除可以得到的所有的合法字符串。

思路和代码

这道题目的思路源自于评论区。刚开始会有点难以理解，现在试图理清这个思路。

先从题目中给的例子入手：()())()
当遍历到第五个括号时，我们发现这个括号的存在非法。因此我们会从当前的三个右括号（下标分别为1, 3, 4）中选择一个删去。那么选择哪个呢？其实选择任意一个右括号都可以使当前的的子字符串合法，并依次生成如下三个结果(())，()()，()()。最后两个结果重复，因此只保留(())，()()两个结果。最终生成的合法字符串为[()()(), (())()]。

这里说明了一种情况，即右括号的数量多于左括号的数量。那么如何处理左括号的数量多于右括号数量的场景呢？如()(()
其实，我们只需要将其倒置为)(()(，并且将)(视为一组合法的括号即可。这时我们会看见下标2上的左括号不合法，对之进行处理即可。方法相同于上一种情况。

还要考虑一个问题，即出现重复的结果集的问题，就像例子中重复生成的的()()。我们如何才能避免使用Set来过滤掉重复的结果呢？

还是举一个例子：()())())
按照之前的处理，当我们遍历到下标4上的右括号时，我们有三个删除选择。而且我们发现当出现连续的右括号时，删除该连续括号中的任意一个产生的结果都相同。所以默认情况下，我们删除第一个括号。这时处理后的字符串为()()())以及(())())。

再对()()())处理，同样的，当我们遇到最后一个右括号时，只需要删除任意一个右括号就可以使数组成为合法数组，那么我们先根据第一个原则，删除连续右括号的第一个括号，可以产生没有重复的结果为(()()),()(())，()()()。

同理(())())可以处理出结果(()())，(())()。其中(()())出现了两次。我们如何避免这样的重复呢？这时我们需要记录一下最后一次删除所在的下标。在该下标前的删除将会产生重复的结果。这里我们看到最后一次删除的下标为3。对下标3之前的删除将会带来重复的结果(()())

public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList<String>();
        removeInvalidParentheses(s, result, 0, 0, new char[]{'(', ')'});
        return result;
    } 
    
    
    
    public void removeInvalidParentheses(String s, List<String> result, int lastRemoveIndex, int lastCheckedIndex, char[] pattern){
        for(int stack = 0, i = lastCheckedIndex ; i<s.length() ; i++){
            int cur = s.charAt(i);
            if(cur == pattern[0]) stack++;
            if(cur == pattern[1]) stack--;
            if(stack>=0) continue;
            for(int j = lastRemoveIndex ; j <= i ; j++){
                if(s.charAt(j)==pattern[1] && (j == lastRemoveIndex || s.charAt(j-1)!=pattern[1])){
                    removeInvalidParentheses(s.substring(0, j) + s.substring(j+1), result, j, i, pattern);
                }
            }
            return;
        }
        String reversed = new StringBuilder(s).reverse().toString();
        if(pattern[0] == '('){
            removeInvalidParentheses(reversed, result, 0, 0, new char[]{')', '('});
        }else{
            result.add(reversed);
        }
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~