题目描述

• 【所有可能结果】-> 【暴力DFS】

思路 && 代码

• 代码比较长，但是总体思路很清晰。
• 剪枝：舍弃左括号、舍弃右括号两种情况（见注释）
• 分情况：当前字符有【左括号】、【右括号】、【字母】三种情况，字母直接取，不影响
• 具体见注释的 Case 分类，有清晰说明
• 去重：先通过 Set 存储所有当前可行解
• 筛选：dfs结束后，len 为删除最小数量无效括号后的字符串长度。用于对 Set 中的有效括号进行筛选。

class Solution {
    int len; // 维护有效字符串的最长值
    public List<String> removeInvalidParentheses(String s) {
        char[] arr = s.toCharArray();
        int right = 0;
        // 右括号计数：用于 dfs 剪枝（选取左括号数量，一定不能大于右括号数量）
        for(char c : arr) {
            if(c == ')') {
                right++;
            }
        }

        // Set 用于去重
        Set<String> set = new HashSet<>();
        dfs(arr, 0, 0, right, new StringBuilder(), set);

        List<String> ans = new ArrayList<>();
        for(String str : set) {
        	// 筛选
            if(str.length() == len) {
                ans.add(str);
            }
        }
        return ans;
    }

    public void dfs(char[] cs, int index, int score, int max, StringBuilder cur, Set<String> ans) {
        // Case 1: 结束
        if(index == cs.length) {
            // 合法，并且长度够的情况
            if(score == 0 && cur.length() >= len) {
                // 加入 Set 中，并且维护 len
                len = cur.length();
                ans.add(cur.toString());
            }
            return;
        }
        // Case 2：当前为左括号
        if(cs[index] == '(') {
            // Case 2.1：选择【加入】当前左括号（如果 score + 1 > max，说明后面右括号【肯定】不够了）
            if(score + 1 <= max) {
                dfs(cs, index + 1, score + 1, max, cur.append('('), ans);
                cur.deleteCharAt(cur.length() - 1);
            }
            // Case 2.2：选择【不加入】当前左括号
            dfs(cs, index + 1, score, max, cur, ans);
        }
        // Case 3：当前为右括号
        else if(cs[index] == ')') {
            // Case 3.1：选择【加入】当前右括号（左边有提供左括号）
            if(score > 0) {
                dfs(cs, index + 1, score - 1, max, cur.append(')'), ans);
                cur.deleteCharAt(cur.length() - 1);
            }
            // Case 3.2：选择【不加入】当前右括号
            dfs(cs, index + 1, score, max, cur, ans);
        }
        // Case 4：当前为字母，直接【加入】，不影响
        else {
            dfs(cs, index + 1, score, max, cur.append(cs[index]), ans);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

• 无注释版

class Solution {
    int len; 
    public List<String> removeInvalidParentheses(String s) {
        char[] arr = s.toCharArray();
        int right = 0;
        for(char c : arr) {
            if(c == ')') {
                right++;
            }
        }
        Set<String> set = new HashSet<>();
        dfs(arr, 0, 0, right, new StringBuilder(), set);
        
        List<String> ans = new ArrayList<>();
        for(String str : set) {
            if(str.length() == len) {
                ans.add(str);
            }
        }
        return ans;
    }

    public void dfs(char[] cs, int index, int score, int max, StringBuilder cur, Set<String> ans) {
        if(index == cs.length) {
            if(score == 0 && cur.length() >= len) {
                len = cur.length();
                ans.add(cur.toString());
            }
            return;
        }
        if(cs[index] == '(') {
            if(score + 1 <= max) {
                dfs(cs, index + 1, score + 1, max, cur.append('('), ans);
                cur.deleteCharAt(cur.length() - 1);
            }
            dfs(cs, index + 1, score, max, cur, ans);
        }
        else if(cs[index] == ')') {
            if(score > 0) {
                dfs(cs, index + 1, score - 1, max, cur.append(')'), ans);
                cur.deleteCharAt(cur.length() - 1);
            }
            dfs(cs, index + 1, score, max, cur, ans);
        }
        else {
            dfs(cs, index + 1, score, max, cur.append(cs[index]), ans);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

二刷

• 二刷懵逼的地方：合法性维护
  1. 靠 score 来进行，众所周知 ‘(’ 随便加，等跑到结尾再算帐 (score == 0）
  2. 但 ‘)’ 不一样，得前面的 ‘(’ 数量够才行。( if(score > 0) )
  3. 由此上两点，可得出合法判断
• 【选出合法结果，维护最长合法长度】-》【由最终长度，筛选较小结果】
• 来了，无剪枝，无效率优化的写法！咱图的就是一个简单明了！摆烂，慢得一
• 具体是少了 StringBuilder、char[] 等优化，但有效代码就 22 行，很简约！

class Solution {
    int maxLen = 0;
    Set<String> set = new HashSet<>();
    public List<String> removeInvalidParentheses(String s) {
        dfs(0, 0, "", s);
        List<String> ans = new ArrayList<>();
        for(String temp : set) {
            if(temp.length() == maxLen) {
                ans.add(temp);
            }
        }
        return ans;
    }
    void dfs(int score, int index, String now, String s) {
        if(index == s.length()) {
            if(score == 0 && now.length() >= maxLen) {
                maxLen = now.length();
                set.add(now);
            } 
        }
        else if(s.charAt(index) == '(') {
            dfs(score + 1, index + 1, now + '(', s);
            dfs(score, index + 1, now, s);
        }
        else if(s.charAt(index) == ')') {
            if(score > 0) {
                dfs(score - 1, index + 1, now + ')', s);
            }
            dfs(score, index + 1, now, s);
        }
        else {
            dfs(score, index + 1, now + s.charAt(index), s);
        }
    }
}