AlgoPressAppearance
题目描述
https://leetcode.cn/problems/remove-invalid-parentheses
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()" 输出：["(())()","()()()"] 示例 2：
输入：s = "(a)())()" 输出：["(a())()","(a)()()"] 示例 3：
输入：s = ")(" 输出：[""]
提示：
1 <= s.length <= 25 s 由小写英文字母以及括号 '(' 和 ')' 组成 s 中至多含 20 个括号
思路
题目要求计算删除最小的括号，可以先计算出必须删除的括号数。 从前往后累计括号数，必须先统计左括号，然后右括号的统计才有意义，最后取 min 表示最多几个左括号和几个右括号。 使用回溯法遍历字符串，当统计到末尾的时候，加入结果集，加入的时候需要去重。
特殊情况： list 为空的时候， list.Add("");
参考代码
csharp
public class Solution {
List<string> list = new List<string>();
private void dfs(string s, string str, int index, int left, int right){
//左括号必须先行
if(index == s.Length){
//如果正好左右括号都用完
if(left == right && left == 0){
if(!list.Contains(str)){
list.Add(str);
}
}
return;
}
//开始添加
char c = s[index];
if(c == '('){
if( left > 0){
dfs(s,str+c,index+1,left-1,right);
}
//尝试舍弃一个(
dfs(s,str,index+1,left,right);
}
else if(c == ')'){
if(right > left){
dfs(s,str+c,index+1,left,right-1);
}
//尝试舍弃一个)
dfs(s,str,index+1,left,right);
}
else{
dfs(s,str+c,index+1,left,right);
}
}
public IList<string> RemoveInvalidParentheses(string s) {
//思路，首先计算合法括号的个数
//然后回溯计算各种可能性的结果，最后插入到 list 中
int left = 0;
int right = 0;
for(int i=0; i<s.Length; i++){
if(s[i] == '('){
left++;
}
else if(s[i] == ')'){
//必须统计合法的 right
if(right < left){
right++;
}
}
}
//最小的括号对数
int min = Math.Min(left,right);
dfs(s,"",0,min,min);
return list;
}
}