301. 删除无效的括号

困难回溯广度优先搜索（逐层删除）力扣原题 ↗

题目描述

输入一个字符串 s，由小写字母和圆括号 (、) 组成。

括号有效是指：每个 ( 都能和它后面的某个 ) 配成一对，每个 ) 也都能和它前面的某个 ( 配对，字母不影响配对。

从 s 中删掉尽量少的括号，使剩下的字符串有效。返回所有删除次数最少时能得到的不同字符串，顺序不限。

示例 1

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

解释：最少删 1 个括号，可得 (())() 或 ()()()。

示例 2

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

解释：字母保留，最少删 1 个括号，有两种结果。

示例 3

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

解释：两个括号都得删掉，只剩空串。

数据范围

1 <= s.length <= 25
s 只含小写英文字母和括号 (、)。
s 中的括号最多 20 个。

解题思路：广度优先搜索（逐层删除）

按“删了几个字符”分层做 BFS：第 0 层只有 s 本身，第 d+1 层是从第 d 层每个字符串中删掉一个括号得到的所有字符串（用集合去重）。第一个出现有效字符串的层就是最少删除次数，把这一层所有有效串返回。判断有效只需一边扫一边维护余额 bal，不能为负且最后为 0。

为什么正确

第 d 层的集合恰好是从 s 删掉 d 个括号能得到的所有不同字符串，且更小的层里没有有效串。

复杂度分析

最坏 O(n·2^n)：各层字符串总数至多 2^n，每个判断和生成需 O(n)。

易错点

找到有效串后要把本层全部检查完再停，不能找到一个就返回；各层必须用集合去重，否则结果重复且规模爆炸；全部删光得到的空串也是有效答案。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        def valid(t):
            bal = 0
            for ch in t:
                if ch == '(':
                    bal += 1
                elif ch == ')':
                    bal -= 1
                    if bal < 0:
                        return False
            return bal == 0

        level = {s}
        while True:
            good = sorted(t for t in level if valid(t))
            if good:
                return good
            nxt = set()
            for t in level:
                for i in range(len(t)):
                    if t[i] in '()':
                        nxt.add(t[:i] + t[i + 1:])
            level = nxt

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        Set<String> level = new TreeSet<>();
        level.add(s);
        while (true) {
            List<String> good = new ArrayList<>();
            for (String t : level) {
                if (valid(t)) good.add(t);
            }
            if (!good.isEmpty()) {
                return good;
            }
            Set<String> nxt = new TreeSet<>();
            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));
                    }
                }
            }
            level = nxt;
        }
    }

    boolean valid(String t) {
        int bal = 0;
        for (char ch : t.toCharArray()) {
            if (ch == '(') {
                bal++;
            } else if (ch == ')') {
                bal--;
                if (bal < 0) {
                    return false;
                }
            }
        }
        return bal == 0;
    }
}

class Solution {
    bool valid(const string& t) {
        int bal = 0;
        for (char ch : t) {
            if (ch == '(') {
                bal++;
            } else if (ch == ')') {
                bal--;
                if (bal < 0) {
                    return false;
                }
            }
        }
        return bal == 0;
    }

public:
    vector<string> removeInvalidParentheses(string s) {
        set<string> level = {s};
        while (true) {
            vector<string> good;
            for (auto& t : level) {
                if (valid(t)) good.push_back(t);
            }
            if (!good.empty()) {
                return good;
            }
            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));
                    }
                }
            }
            level = nxt;
        }
    }
};

func removeInvalidParentheses(s string) []string {
	valid := func(t string) bool {
		bal := 0
		for _, ch := range t {
			if ch == '(' {
				bal++
			} else if ch == ')' {
				bal--
				if bal < 0 {
					return false
				}
			}
		}
		return bal == 0
	}
	level := map[string]bool{s: true}
	for {
		good := []string{}
		for t := range level {
			if valid(t) {
				good = append(good, t)
			}
		}
		if len(good) > 0 {
			sort.Strings(good)
			return good
		}
		nxt := map[string]bool{}
		for t := range level {
			for i := 0; i < len(t); i++ {
				if t[i] == '(' || t[i] == ')' {
					nxt[t[:i]+t[i+1:]] = true
				}
			}
		}
		level = nxt
	}
}

var removeInvalidParentheses = function(s) {
    const valid = (t) => {
        let bal = 0;
        for (const ch of t) {
            if (ch === '(') {
                bal++;
            } else if (ch === ')') {
                bal--;
                if (bal < 0) {
                    return false;
                }
            }
        }
        return bal === 0;
    };
    let level = new Set([s]);
    while (true) {
        const good = [...level].filter(valid).sort();
        if (good.length > 0) {
            return good;
        }
        const nxt = new Set();
        for (const t of level) {
            for (let i = 0; i < t.length; i++) {
                if (t[i] === '(' || t[i] === ')') {
                    nxt.add(t.slice(0, i) + t.slice(i + 1));
                }
            }
        }
        level = nxt;
    }
};

function removeInvalidParentheses(s: string): string[] {
    const valid = (t: string): boolean => {
        let bal = 0;
        for (const ch of t) {
            if (ch === '(') {
                bal++;
            } else if (ch === ')') {
                bal--;
                if (bal < 0) {
                    return false;
                }
            }
        }
        return bal === 0;
    };
    let level = new Set<string>([s]);
    while (true) {
        const good = [...level].filter(valid).sort();
        if (good.length > 0) {
            return good;
        }
        const nxt = new Set<string>();
        for (const t of level) {
            for (let i = 0; i < t.length; i++) {
                if (t[i] === '(' || t[i] === ')') {
                    nxt.add(t.slice(0, i) + t.slice(i + 1));
                }
            }
        }
        level = nxt;
    }
}

载入编辑器，自己跑一遍 →

其他解法

BFS 每层多删一个括号，第一层出现合法串就是最少删除，不需要预先知道删几个，但要用集合保存整层候选；回溯先算出要删的左右括号数量，再带剪枝地枚举删除位置，内存占用小。

解法 2：回溯 + 剪枝时间 O(n · 2^n)，空间 O(n²)

先扫一遍算出至少要删的左括号数 l 和右括号数 r：遇到 '(' 时 l++；遇到 ')' 时，若 l > 0 则 l--，否则 r++。然后回溯，从上次删除的位置往后尝试删一个 '(' 或 ')'。连续相同字符只删第一个来去重；剩余字符不够删时剪枝。l 和 r 都归零时，如果字符串合法就加入答案。

先确定最少删除数，只枚举删恰好这么多个的方案，并用“从上次位置继续”和“跳过重复字符”去重，不用像 BFS 那样保存整层字符串集合，内存更省。剪枝和去重条件需要仔细推导。

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        l = r = 0
        for ch in s:
            if ch == '(':
                l += 1
            elif ch == ')':
                if l > 0:
                    l -= 1
                else:
                    r += 1

        def valid(t):
            bal = 0
            for ch in t:
                if ch == '(':
                    bal += 1
                elif ch == ')':
                    bal -= 1
                    if bal < 0:
                        return False
            return bal == 0

        res = []

        def dfs(t, start, l, r):
            if l == 0 and r == 0:
                if valid(t):
                    res.append(t)
                return
            for i in range(start, len(t)):
                if l + r > len(t) - i:
                    break
                if i > start and t[i] == t[i - 1]:
                    continue
                if l > 0 and t[i] == '(':
                    dfs(t[:i] + t[i + 1:], i, l - 1, r)
                if r > 0 and t[i] == ')':
                    dfs(t[:i] + t[i + 1:], i, l, r - 1)

        dfs(s, 0, l, r)
        return res

class Solution {
    private List<String> res = new ArrayList<>();

    private boolean valid(String t) {
        int bal = 0;
        for (char ch : t.toCharArray()) {
            if (ch == '(') bal++;
            else if (ch == ')' && --bal < 0) return false;
        }
        return bal == 0;
    }

    private void dfs(String t, int start, int l, int r) {
        if (l == 0 && r == 0) {
            if (valid(t)) res.add(t);
            return;
        }
        for (int i = start; i < t.length(); i++) {
            if (l + r > t.length() - i) break;
            if (i > start && t.charAt(i) == t.charAt(i - 1)) continue;
            if (l > 0 && t.charAt(i) == '(') dfs(t.substring(0, i) + t.substring(i + 1), i, l - 1, r);
            if (r > 0 && t.charAt(i) == ')') dfs(t.substring(0, i) + t.substring(i + 1), i, l, r - 1);
        }
    }

    public List<String> removeInvalidParentheses(String s) {
        int l = 0, r = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '(') l++;
            else if (ch == ')') {
                if (l > 0) l--;
                else r++;
            }
        }
        dfs(s, 0, l, r);
        return res;
    }
}

class Solution {
    vector<string> res;

    bool valid(const string& t) {
        int bal = 0;
        for (char ch : t) {
            if (ch == '(') bal++;
            else if (ch == ')' && --bal < 0) return false;
        }
        return bal == 0;
    }

    void dfs(const string& t, int start, int l, int r) {
        if (l == 0 && r == 0) {
            if (valid(t)) res.push_back(t);
            return;
        }
        for (int i = start; i < (int)t.size(); i++) {
            if (l + r > (int)t.size() - i) break;
            if (i > start && t[i] == t[i - 1]) continue;
            if (l > 0 && t[i] == '(') dfs(t.substr(0, i) + t.substr(i + 1), i, l - 1, r);
            if (r > 0 && t[i] == ')') dfs(t.substr(0, i) + t.substr(i + 1), i, l, r - 1);
        }
    }

public:
    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for (char ch : s) {
            if (ch == '(') l++;
            else if (ch == ')') {
                if (l > 0) l--;
                else r++;
            }
        }
        dfs(s, 0, l, r);
        return res;
    }
};

func removeInvalidParentheses(s string) []string {
	l, r := 0, 0
	for _, ch := range s {
		if ch == '(' {
			l++
		} else if ch == ')' {
			if l > 0 {
				l--
			} else {
				r++
			}
		}
	}
	valid := func(t string) bool {
		bal := 0
		for _, ch := range t {
			if ch == '(' {
				bal++
			} else if ch == ')' {
				bal--
				if bal < 0 {
					return false
				}
			}
		}
		return bal == 0
	}
	res := []string{}
	var dfs func(t string, start, l, r int)
	dfs = func(t string, start, l, r int) {
		if l == 0 && r == 0 {
			if valid(t) {
				res = append(res, t)
			}
			return
		}
		for i := start; i < len(t); i++ {
			if l+r > len(t)-i {
				break
			}
			if i > start && t[i] == t[i-1] {
				continue
			}
			if l > 0 && t[i] == '(' {
				dfs(t[:i]+t[i+1:], i, l-1, r)
			}
			if r > 0 && t[i] == ')' {
				dfs(t[:i]+t[i+1:], i, l, r-1)
			}
		}
	}
	dfs(s, 0, l, r)
	return res
}

var removeInvalidParentheses = function(s) {
    let l = 0, r = 0;
    for (const ch of s) {
        if (ch === '(') l++;
        else if (ch === ')') {
            if (l > 0) l--;
            else r++;
        }
    }
    const valid = (t) => {
        let bal = 0;
        for (const ch of t) {
            if (ch === '(') bal++;
            else if (ch === ')' && --bal < 0) return false;
        }
        return bal === 0;
    };
    const res = [];
    const dfs = (t, start, l, r) => {
        if (l === 0 && r === 0) {
            if (valid(t)) res.push(t);
            return;
        }
        for (let i = start; i < t.length; i++) {
            if (l + r > t.length - i) break;
            if (i > start && t[i] === t[i - 1]) continue;
            if (l > 0 && t[i] === '(') dfs(t.slice(0, i) + t.slice(i + 1), i, l - 1, r);
            if (r > 0 && t[i] === ')') dfs(t.slice(0, i) + t.slice(i + 1), i, l, r - 1);
        }
    };
    dfs(s, 0, l, r);
    return res;
};

function removeInvalidParentheses(s: string): string[] {
    let l = 0, r = 0;
    for (const ch of s) {
        if (ch === '(') l++;
        else if (ch === ')') {
            if (l > 0) l--;
            else r++;
        }
    }
    const valid = (t: string): boolean => {
        let bal = 0;
        for (const ch of t) {
            if (ch === '(') bal++;
            else if (ch === ')' && --bal < 0) return false;
        }
        return bal === 0;
    };
    const res: string[] = [];
    const dfs = (t: string, start: number, l: number, r: number): void => {
        if (l === 0 && r === 0) {
            if (valid(t)) res.push(t);
            return;
        }
        for (let i = start; i < t.length; i++) {
            if (l + r > t.length - i) break;
            if (i > start && t[i] === t[i - 1]) continue;
            if (l > 0 && t[i] === '(') dfs(t.slice(0, i) + t.slice(i + 1), i, l - 1, r);
            if (r > 0 && t[i] === ')') dfs(t.slice(0, i) + t.slice(i + 1), i, l, r - 1);
        }
    };
    dfs(s, 0, l, r);
    return res;
}

回溯专题的其他题目

查看回溯全部题目 →