删除无效的括号 - Stellar Observer Protocol

960 字

5 分钟

删除无效的括号

2025-08-09

Algorithms

字符串

/

回溯

/

广度优先搜索

题目描述#

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

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

解题思路#

最小删除量计算：遍历字符串，统计未匹配的左右括号数量 lremove/rremove（需删除的最少括号数）。
回溯搜索：从起始位置遍历字符串，递归尝试删除每个无效括号：
- 跳过连续重复括号避免重复解
- 剩余字符不足时剪枝
- 删除左括号或右括号后更新对应删除量
结果验证：当删除量归零时，用栈验证括号有效性：
- 遇左括号计数+1，遇右括号计数-1
- 中途出现负值立即终止
- 最终计数为零则为有效解

关键洞察#

删除量确定性：最小删除量 (lremove,rremove) 是固定值，直接作为搜索边界。
重复括号优化：跳过连续相同括号（str[i] === str[i-1]），避免生成重复解。
双效剪枝：
- 资源剪枝：剩余字符数 < lremove+rremove 时终止
- 逻辑剪枝：优先删除无效括号缩小搜索空间
延迟验证：仅在删除完成时检查有效性，减少中间状态验证开销。

复杂度分析#

指标	说明
时间复杂度	O(n·2^n)：最坏情况每个括号有删/留选择（n≤25 实际剪枝高效）
空间复杂度	O(n²)：递归深度 O(n)，每层 `substr` 创建新字符串（O(n)）
验证复杂度	O(n)：`isValid` 单次遍历，仅终点调用

注：剪枝策略使实际性能远优于理论最坏复杂度，字符串约束（n≤25）保证可行性。

代码实现#

递归版本

1
/**
2
 * @link {https://leetcode.cn/problems/remove-invalid-parentheses}
3
 * @param {string} s
4
 * @return {string[]}
5
 */
6
var removeInvalidParentheses = function(s) {
7
    const helper = (str, start, lremove, rremove) => {
8
        if (lremove === 0 && rremove === 0) {
9
            if (isValid(str)) {
10
                res.push(str);
11
            }
12
            return;
13
        }
14
        for (let i = start; i < str.length; i++) {
15
            if (i !== start && str[i] === str[i - 1]) {
16
                continue;
17
            }
18
            // 如果剩余的字符无法满足去掉的数量要求，直接返回
19
            if (lremove + rremove > str.length - i) {
20
                return;
21
            }
22
            // 尝试去掉一个左括号
23
            if (lremove > 0 && str[i] === '(') {
24
                helper(str.substr(0, i) + str.substr(i + 1), i, lremove - 1, rremove);
25
            }
26
            // 尝试去掉一个右括号
27
            if (rremove > 0 && str[i] === ')') {
28
                helper(str.substr(0, i) + str.substr(i + 1), i, lremove, rremove - 1);
29
            }
30
        }
31
    }
32
    const res = [];
33
    let lremove = 0;
34
    let rremove = 0;
35
    for (const c of s) {
36
        if (c === '(') {
37
            lremove++;
38
        } else if (c === ')') {
39
            if (lremove === 0) {
40
                rremove++;
41
            } else {
42
                lremove--;
43
            }
44
        }
45
    }
46
    helper(s, 0, lremove, rremove);
47
    return res;
48
}
49
const isValid = (str) => {
50
    let cnt = 0;
51

52
    for (let i = 0; i < str.length; i++) {
53
        if (str[i] === '(') {
54
            cnt++;
55
        } else if (str[i] === ')') {
56
            cnt--;
57
            if (cnt < 0) {
58
                return false;
59
            }
60
        }
61
    }
62
    return cnt === 0;
63
}

迭代版本

1
const removeInvalidParentheses = (s) => {
2
    const isValid = (str) => {
3
        let balance = 0;
4
        for (const c of str) {
5
            if (c === '(') balance++;
6
            else if (c === ')') balance--;
7
            if (balance < 0) return false;
8
        }
9
        return balance === 0;
10
    };
11

12
    let queue = new Set([s]);
13
    while (queue.size) {
14
        const nextQueue = new Set();
15
        const validResults = [];
16

17
        for (const expr of queue) {
18
            if (isValid(expr)) {
19
                validResults.push(expr);
20
            }
21
            // 找到有效表达式后停止生成下一层
22
            if (validResults.length) continue;
23

24
            // 生成所有删除一个括号的表达式
25
            for (let i = 0; i < expr.length; i++) {
26
                if (expr[i] !== '(' && expr[i] !== ')') continue;
27
                const newExpr = expr.slice(0, i) + expr.slice(i + 1);
28
                nextQueue.add(newExpr);
29
            }
30
        }
31

32
        if (validResults.length) return validResults;
33
        queue = nextQueue;
34
    }
35
    return [""];
36
};