删除无效的括号 图解题解

这题不是只求一个合法字符串

LeetCode 301 要求删除最少数量的无效括号，并返回这个最少删除数下的所有不同结果。比如 `()())()` 只需删除一个右括号，但有 `(())()` 和 `()()()` 两个答案，返回任意一个都不完整。

两遍贪心可以在线性时间构造一个最少删除的合法串，适合 LC1249；它无法枚举同样少删的所有不同结果，因此不能作为 LC301 的完整主解。

为什么分层 BFS 天然保证删除最少

把原字符串放在第 0 层。从某个状态删除一个左括号或右括号，就得到下一层状态。因此第 d 层中的每个字符串都恰好删除了 d 个括号。

BFS 按 0、1、2……的顺序检查删除次数。只要前面各层都没有合法串，而第 d 层第一次出现合法串，就能直接证明最少删除数是 d；更深层都会删除更多，没有继续搜索的价值。

怎样在线性时间验证一个候选

用 balance 记录当前尚未匹配的左括号数：遇到 `(` 加一，遇到 `)` 减一，字母跳过。如果扫描途中 balance 变成负数，说明当前右括号左侧没有可匹配的左括号，候选立即无效。

扫描结束时 balance 还必须等于 0。大于 0 表示仍有左括号没有右括号配对。于是一个候选的验证时间是 O(n)，而且字母会原样保留。

为什么要去重，而且要检查完整个命中层

删除相邻的相同括号经常得到同一个字符串。例如从连续的两个右括号中删除任意一个，结果可能完全相同。每层使用集合保存状态，能避免重复入队、重复验证和重复输出。

在某一层找到第一个合法串时不能立刻返回。同层其他状态删除的括号数量完全相同，也可能是最优答案。正确停止方式是：检查完整个当前层，收集本层所有合法串；若集合非空，就返回它们，并且不再生成下一层。

正确性可以拆成最少性与完整性

最少性来自 BFS 层序：首次命中层之前的所有较少删除方案已经被完整验证，均不合法；首次命中层之后的状态删除更多，不可能更优。

完整性来自扩展规则与整层收集：每个状态都尝试删除每一个括号，所以所有删除 d 个括号的候选都会被覆盖；集合只合并内容相同的状态，不会丢掉不同结果；首次命中层又会被完整扫描，因此该层所有不同的合法串都会进入答案。

复杂度、边界与 DFS 替代方案

括号的删除子集最坏可达指数数量，每个候选还需 O(n) 验证或构造，所以时间复杂度最坏为 O(n·2^n)，空间最坏为 O(2^n)。BFS 的价值是最少性直观，并通过按层停止避免搜索更深状态，不是把指数问题变成多项式。

原串已经合法时，第 0 层直接返回它；`)(` 这类输入最终返回空串；纯字母串原样返回。也可以先统计必须删除的左右括号数，再用 DFS 加剩余字符剪枝枚举答案，通常更省层集合空间，但正确性仍要同时说明最少和不漏。

Python

class Solution:
    # ① 两遍贪心：删最少 → 得到「一个」合法串（LC1249 的完整解）
    def removeInvalid(self, s):
        arr = list(s)
        def scan(idx, op, cl):          # idx 顺序, op 开括号, cl 闭括号
            bal = 0
            for i in idx:
                if arr[i] == op: bal += 1
                elif arr[i] == cl:
                    if bal > 0: bal -= 1
                    else: arr[i] = ''      # 多余,删除
        scan(range(len(arr)), '(', ')')    # 第一遍 删多余 )
        scan(reversed(range(len(arr))), ')', '(')  # 第二遍 删多余 (
        return ''.join(arr)

    # ② 真题 LC301：返回「所有」删最少后的合法结果（逐层 BFS）
    def isValid(self, t):
        bal = 0
        for ch in t:
            if ch == '(': bal += 1
            elif ch == ')':
                bal -= 1
                if bal < 0: return False
        return bal == 0

    def removeInvalidParentheses(self, s):
        level = {s}
        while True:
            res = [t for t in level if self.isValid(t)]
            if res: return res           # 这一层有解 = 删得最少
            nxt = set()
            for t in level:
                for i, ch in enumerate(t):
                    if ch in '()':       # 每次只删一个括号
                        nxt.add(t[:i] + t[i+1:])
            if not nxt: return ['']
            level = nxt

C++

class Solution {
public:
    // ① 两遍贪心：删最少 → 得到「一个」合法串（LC1249 的完整解）
    string removeInvalid(string s){
        auto scan=[&](bool fwd,char op,char cl){
            int bal=0, n=s.size();
            for(int k=0;k<n;k++){
                int i = fwd ? k : n-1-k;
                if(s[i]==op) bal++;
                else if(s[i]==cl){ if(bal>0) bal--; else s[i]='*'; }
            }
        };
        scan(true,'(',')'); scan(false,')','(');
        string r; for(char c:s) if(c!='*') r+=c; return r;
    }

    // ② 真题 LC301：返回「所有」删最少后的合法结果（逐层 BFS）
    bool isValid(const string& t){
        int bal=0;
        for(char c:t){
            if(c=='(') bal++;
            else if(c==')' && --bal<0) return false;
        }
        return bal==0;
    }
    vector<string> removeInvalidParentheses(string s){
        unordered_set<string> level{s};
        while(true){
            vector<string> res;
            for(auto& t:level) if(isValid(t)) res.push_back(t);
            if(!res.empty()) return res;      // 这一层有解 = 删得最少
            unordered_set<string> nxt;
            for(auto& t:level)
                for(int i=0;i<(int)t.size();i++)
                    if(t[i]=='('||t[i]==')')  // 每次只删一个括号
                        nxt.insert(t.substr(0,i)+t.substr(i+1));
            if(nxt.empty()) return {""};
            level = nxt;
        }
    }
};

Java

class Solution {
    // ① 两遍贪心：删最少 → 得到「一个」合法串（LC1249 的完整解）
    String removeInvalid(String s){
        char[] a = s.toCharArray();
        scan(a, true,  '(', ')');   // 第一遍 删多余 )
        scan(a, false, ')', '(');   // 第二遍 删多余 (
        StringBuilder r = new StringBuilder();
        for (char c : a) if (c != 0) r.append(c);
        return r.toString();
    }
    void scan(char[] a, boolean fwd, char op, char cl){
        int bal = 0, n = a.length;
        for (int k = 0; k < n; k++){
            int i = fwd ? k : n-1-k;
            if (a[i]==op) bal++;
            else if (a[i]==cl){ if(bal>0) bal--; else a[i]=0; }
        }
    }

    // ② 真题 LC301：返回「所有」删最少后的合法结果（逐层 BFS）
    boolean isValid(String t){
        int bal = 0;
        for (char c : t.toCharArray()){
            if (c=='(') bal++;
            else if (c==')' && --bal < 0) return false;
        }
        return bal == 0;
    }
    public List<String> removeInvalidParentheses(String s){
        Set<String> level = new HashSet<>();
        level.add(s);
        while (true){
            List<String> res = new ArrayList<>();
            for (String t : level) if (isValid(t)) res.add(t);
            if (!res.isEmpty()) return res;   // 这一层有解 = 删得最少
            Set<String> nxt = new HashSet<>();
            for (String t : level)
                for (int i = 0; i < t.length(); i++){
                    char c = t.charAt(i);
                    if (c=='('||c==')')       // 每次只删一个括号
                        nxt.add(t.substring(0,i)+t.substring(i+1));
                }
            if (nxt.isEmpty()) return Collections.singletonList("");
            level = nxt;
        }
    }
}