301. 移除无效的括号

Hard

题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= s.length <= 25
s 由小写英文字母以及括号 '(' 和 ')' 组成
输入字符串中含有最多 20 个括号

解题思路

这道题要求删除最少数量的无效括号来得到有效的字符串组合。我们可以采用BFS广度优先搜索的方法来解决。

核心思路：

先预处理计算需要删除的左括号和右括号数量
使用DFS回溯遍历所有可能的删除组合
对于每个字符，我们有三种选择：保留、删除（如果是左括号且还需删除左括号）、删除（如果是右括号且还需删除右括号）
在遍历过程中维护当前的平衡状态，确保右括号数量不超过左括号
当删除完指定数量的括号且字符串平衡时，将结果加入答案集

算法步骤：

首先统计需要删除的多余左括号和右括号数量
使用DFS遍历字符串，对每个括号字符进行保留或删除的决策
维护当前字符串的左右括号平衡状态
使用set去重，确保结果唯一性

这种方法能够保证找到所有删除最少括号的有效组合，时间复杂度相对较优。

代码实现

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        // 计算需要删除的左括号和右括号数量
        int left = 0, right = 0;
        for (char c : s) {
            if (c == '(') {
                left++;
            } else if (c == ')') {
                if (left > 0) {
                    left--;
                } else {
                    right++;
                }
            }
        }
        
        set<string> result;
        dfs(s, 0, left, right, 0, "", result);
        return vector<string>(result.begin(), result.end());
    }
    
private:
    void dfs(string s, int index, int leftRem, int rightRem, int leftCount, string path, set<string>& result) {
        if (index == s.length()) {
            if (leftRem == 0 && rightRem == 0 && leftCount == 0) {
                result.insert(path);
            }
            return;
        }
        
        char c = s[index];
        
        // 删除当前字符的情况
        if ((c == '(' && leftRem > 0) || (c == ')' && rightRem > 0)) {
            dfs(s, index + 1, leftRem - (c == '(' ? 1 : 0), rightRem - (c == ')' ? 1 : 0), leftCount, path, result);
        }
        
        // 保留当前字符的情况
        path += c;
        if (c != '(' && c != ')') {
            dfs(s, index + 1, leftRem, rightRem, leftCount, path, result);
        } else if (c == '(') {
            dfs(s, index + 1, leftRem, rightRem, leftCount + 1, path, result);
        } else if (c == ')' && leftCount > 0) {
            dfs(s, index + 1, leftRem, rightRem, leftCount - 1, path, result);
        }
    }
};

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # 计算需要删除的左括号和右括号数量
        left = right = 0
        for c in s:
            if c == '(':
                left += 1
            elif c == ')':
                if left > 0:
                    left -= 1
                else:
                    right += 1
        
        result = set()
        
        def dfs(index, left_rem, right_rem, left_count, path):
            if index == len(s):
                if left_rem == 0 and right_rem == 0 and left_count == 0:
                    result.add(path)
                return
            
            c = s[index]
            
            # 删除当前字符的情况
            if (c == '(' and left_rem > 0) or (c == ')' and right_rem > 0):
                dfs(index + 1, left_rem - (1 if c == '(' else 0), right_rem - (1 if c == ')' else 0), left_count, path)
            
            # 保留当前字符的情况
            if c not in '()':
                dfs(index + 1, left_rem, right_rem, left_count, path + c)
            elif c == '(':
                dfs(index + 1, left_rem, right_rem, left_count + 1, path + c)
            elif c == ')' and left_count > 0:
                dfs(index + 1, left_rem, right_rem, left_count - 1, path + c)
        
        dfs(0, left, right, 0, "")
        return list(result)

public class Solution {
    public IList<string> RemoveInvalidParentheses(string s) {
        // 计算需要删除的左括号和右括号数量
        int left = 0, right = 0;
        foreach (char c in s) {
            if (c == '(') {
                left++;
            } else if (c == ')') {
                if (left > 0) {
                    left--;
                } else {
                    right++;
                }
            }
        }
        
        HashSet<string> result = new HashSet<string>();
        DFS(s, 0, left, right, 0, "", result);
        return result.ToList();
    }
    
    private void DFS(string s, int index, int leftRem, int rightRem, int leftCount, string path, HashSet<string> result) {
        if (index == s.Length) {
            if (leftRem == 0 && rightRem == 0 && leftCount == 0) {
                result.Add(path);
            }
            return;
        }
        
        char c = s[index];
        
        // 删除当前字符的情况
        if ((c == '(' && leftRem > 0) || (c == ')' && rightRem > 0)) {
            DFS(s, index + 1, leftRem - (c == '(' ? 1 : 0), rightRem - (c == ')' ? 1 : 0), leftCount, path, result);
        }
        
        // 保留当前字符的情况
        path += c;
        if (c != '(' && c != ')') {
            DFS(s, index + 1, leftRem, rightRem, leftCount, path, result);
        } else if (c == '(') {
            DFS(s, index + 1, leftRem, rightRem, leftCount + 1, path, result);
        } else if (c == ')' && leftCount > 0) {
            DFS(s, index + 1, leftRem, rightRem, leftCount - 1, path, result);
        }
    }
}

var removeInvalidParentheses = function(s) {
    function isValid(str) {
        let count = 0;
        for (let char of str) {
            if (char === '(') count++;
            else if (char === ')') {
                count--;
                if (count < 0) return false;
            }
        }
        return count === 0;
    }
    
    let queue = [s];
    let visited = new Set([s]);
    let found = false;
    
    while (queue.length > 0) {
        let size = queue.length;
        
        for (let i = 0; i < size; i++) {
            let current = queue.shift();
            
            if (isValid(current)) {
                found = true;
                queue.push(current);
            }
            
            if (!found) {
                for (let j = 0; j < current.length; j++) {
                    if (current[j] === '(' || current[j] === ')') {
                        let next = current.slice(0, j) + current.slice(j + 1);
                        if (!visited.has(next)) {
                            visited.add(next);
                            queue.push(next);
                        }
                    }
                }
            }
        }
        
        if (found) break;
    }
    
    return queue.filter(str => isValid(str));
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(2^n)，其中 n 是字符串长度。最坏情况下需要尝试删除或保留每个字符的所有组合
空间复杂度	O(2^n)，递归调用栈的深度最大为 n，结果集合可能包含指数级别的字符串

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目