【LeetCode】301. 删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

输入：s = ")("
输出：[""]

提示：

• 1 <= s.length <= 25 s
• 由小写英文字母以及括号 '(' 和 ')' 组成
• s 中至多含 20 个括号

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-invalid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：存在不合理的括号，删掉最少的括号，保证括号合理。
当前位置有两种选择，取或者不取。使得拼接的字符串最长，同时要保证括号的合理

该题解能通过，但是时间太长，有时间再想优化的方法，或者使用其他方法

class Solution {
    // 
    int max = Integer.MIN_VALUE;
    List<String> ret = new ArrayList<>();
    public List<String> removeInvalidParentheses(String s) {
        dfs(s,0,"",0,0);
        return ret;

    }

    /**
    
    当前位置有两种选择， 取或者不取
     */
    private void dfs(String s, int index, String str, int lNum, int rNum) {
        // 不符合要求的直接返回
        if(rNum > lNum) {
            return;
        }
        if(index == s.length() ) {
            if(lNum != rNum) {
                return;
            }


            if( max < str.length()) {
                max = str.length();
                ret.clear();

            }
            if(max == str.length()) {
                if(!ret.contains(str)) {
                    ret.add(str);
                }
                
            }
            return;
        }

        char c = s.charAt(index);
        if(Character.isLetter(c)) {
            dfs(s,index+1,str + c,lNum,rNum);
        } else {
            dfs(s,index+1,str,lNum,rNum);
            if(c == '(') {
                lNum = lNum+1;
            } else {
                rNum = rNum + 1;
            }
            dfs(s,index+1,str + c,lNum,rNum);
           

        }

    }
}