LeetCode Remove Invalid Parentheses - 移除最少括號使字符串有效

題目大意

給定包含括號和字母的字符串，移除最少數量的括號使其有效，返回所有可能的結果（去重）。例："()())()" → ["()()()", "(())()"]，"(a)())()" → ["(a)()()", "(a())()"]，")(" → [""]。

DFS + 剪枝策略

遞歸遍歷字符串，維護：

• countLeft：當前未匹配的左括號數
• maxLeft：歷史最大匹配左括號數（用於優先保留更長結果）

每字符三種情況：

1. '('：優先保留（遞歸 countLeft+1, maxLeft+1），再嘗試刪除（遞歸 countLeft, maxLeft）。保證最長結果先生成。
2. ')'：若 countLeft > 0 可保留（countLeft-1）；無論如何均可刪除（countLeft 不變）。
3. 其他字符：必須保留。

終止條件：字符串處理完。若 countLeft==0 且結果非空，按 maxLeft 更新全局最大匹配數，收集結果。

代碼實現 (Java)

public class Solution {
    private List res = new ArrayList<>();
    private int max = 0;

    public List removeInvalidParentheses(String s) {
        dfs(s, "", 0, 0);
        if (res.isEmpty()) res.add("");
        return res;
    }

    private void dfs(String str, String cur, int countLeft, int maxLeft) {
        if (str.isEmpty()) {
            if (countLeft == 0 && !cur.isEmpty()) {
                if (maxLeft > max) max = maxLeft;
                if (maxLeft == max && !res.contains(cur)) res.add(cur);
            }
            return;
        }
        char c = str.charAt(0);
        String rest = str.substring(1);
        if (c == '(') {
            dfs(rest, cur + '(', countLeft + 1, maxLeft + 1); // 保留
            dfs(rest, cur, countLeft, maxLeft);               // 刪除
        } else if (c == ')') {
            if (countLeft > 0)
                dfs(rest, cur + ')', countLeft - 1, maxLeft); // 保留匹配
            dfs(rest, cur, countLeft, maxLeft);               // 刪除
        } else {
            dfs(rest, cur + c, countLeft, maxLeft);           // 字母必保留
        }
    }
}

優化：預計算需刪除的左右括號數 (BFS/雙指針預處理)

先掃描字符串算出 leftRem（多餘左括號數）和 rightRem（多餘右括號數），DFS 時強制刪除恰好這些數量，避免探索多餘分支。此法更快但代碼稍長。

複雜度

• 時間：指數級（最壯情況），但剪枝極強，實際極快。
• 空間：O(n) 遞歸棧 + 結果存儲。

關鍵點總結

1. 優先保留左括號 確保最長有效串先生成，配合 maxLeft 去重收集。
2. 右括號匹配邏輯：countLeft > 0 才可保留。
3. 結果去重用 Set 或 !res.contains()。
4. 空串特判：若無有效非空串，返回 [""]。