回溯题目：删除无效的括号

题目

标题和出处

标题：删除无效的括号

出处：301. 删除无效的括号

难度

8 级

题目描述

要求

给定一个由括号和字母组成的字符串s \texttt{s}s，删除最小数量的无效括号，使得输入的字符串有效。

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

示例

示例 1：

输入：s = "()())()" \texttt{s = "()())()"}s = "()())()"
输出：["(())()","()()()"] \texttt{["(())()","()()()"]}["(())()","()()()"]

示例 2：

输入：s = "(a)())()" \texttt{s = "(a)())()"}s = "(a)())()"
输出：["(a())()","(a)()()"] \texttt{["(a())()","(a)()()"]}["(a())()","(a)()()"]

示例 3：

输入：s = ")(" \texttt{s = ")("}s = ")("
输出：[""] \texttt{[""]}[""]

数据范围

• 1 ≤ s.length ≤ 25 \texttt{1} \le \texttt{s.length} \le \texttt{25}1≤s.length≤25
• s \texttt{s}s由小写英语字母以及括号‘(’ \texttt{`('}‘(’和‘)’ \texttt{`)'}‘)’组成
• s \texttt{s}s中至多含20 \texttt{20}20个括号

解法一

思路和算法

这道题要求从字符串s ss中删除最少数量的无效括号，使得字符串中剩余的字符有效。最少操作符合广度优先搜索的应用场景，因此可以使用广度优先搜索得到删除次数最少的情况下的全部有效字符串。

广度优先搜索的做法是，对于字符串中的每个括号，将其删除之后得到一个新的字符串，将新的字符串在下一轮搜索。

第0 00轮遍历初始字符串s ss，第i ii轮遍历所有删除i ii个括号之后的字符串，即每一轮遍历的字符串的长度依次递减。对于当前轮的全部字符串，判断每个字符串是否有效，如果有效则将其添加到答案中。如果一轮结束之后，答案不为空，则找到删除次数最少的情况下的全部有效字符串，此时结束搜索，返回答案。

实现方面有以下两点说明。

1. 如果当前字符串中有两个相邻的相同括号字符，则删除其中任意一个括号字符得到的新字符串是相同的，因此只需要考虑删除其中一个括号字符得到的新字符串，跳过相邻的其余相同括号字符。

2. 使用哈希集合存储每一轮遍历的字符串，可以确保同一个字符串只访问一次。

代码

classSolution{publicList<String>removeInvalidParentheses(Strings){List<String>valid=newArrayList<String>();Set<String>set=newHashSet<String>();set.add(s);while(!set.isEmpty()){for(Stringstr:set){if(isValid(str)){valid.add(str);}}if(!valid.isEmpty()){break;}Set<String>nextSet=newHashSet<String>();for(Stringstr:set){intlength=str.length();for(inti=0;i<length;i++){charc=str.charAt(i);if((i>0&&c==str.charAt(i-1))||(c!='('&&c!=')')){continue;}StringnextStr=str.substring(0,i)+str.substring(i+1);nextSet.add(nextStr);}}set=nextSet;}returnvalid;}publicbooleanisValid(Stringstr){intcount=0;intlength=str.length();for(inti=0;i<length;i++){charc=str.charAt(i);if(c=='('){count++;}elseif(c==')'){count--;}if(count<0){returnfalse;}}returncount==0;}}

复杂度分析

• 时间复杂度：O ( n 2 × 2 n ) O(n^2 \times 2^n)O(n2×2n)，其中n nn是字符串s ss的长度。字符串s ss最多有2 n 2^n2n个子序列，因此广度优先搜索的过程中最多遍历2 n 2^n2n个不同的字符串，对于每个字符串的操作时间是O ( n 2 ) O(n^2)O(n2)的时间，将每个有效字符串添加到答案需要O ( n ) O(n)O(n)的时间，因此时间复杂度是O ( n 2 × 2 n ) O(n^2 \times 2^n)O(n2×2n)。

• 空间复杂度：O ( n × 2 n ) O(n \times 2^n)O(n×2n)，其中n nn是字符串s ss的长度。字符串s ss最多有2 n 2^n2n个子序列，因此广度优先搜索的过程中最多遍历2 n 2^n2n个不同的字符串，每个字符串的长度不超过n nn，因此空间复杂度是O ( n × 2 n ) O(n \times 2^n)O(n×2n)。

解法二

思路和算法

也可以使用回溯的做法得到删除次数最少的情况下的全部有效字符串。

由于回溯本身不保证得到最少操作的答案，因此需要首先遍历字符串得到左括号和右括号的最少删除次数。计算左括号和右括号的最少删除次数时，需要考虑剩余的左括号和右括号的个数相等且任意前缀中的左括号个数大于等于右括号个数。具体做法是，使用leftRemove \textit{leftRemove}leftRemove和rightRemove \textit{rightRemove}rightRemove分别表示左括号和右括号的最少删除次数，从左到右遍历字符串s ss，执行如下操作。

• 如果遇到左括号，则将leftRemove \textit{leftRemove}leftRemove加1 11。

• 如果遇到右括号，则当leftRemove = 0 \textit{leftRemove} = 0leftRemove=0时将rightRemove \textit{rightRemove}rightRemove加1 11，当leftRemove > 0 \textit{leftRemove} > 0leftRemove>0时将leftRemove \textit{leftRemove}leftRemove减1 11。

根据有效括号的定义，一定可以从s ss中删除leftRemove \textit{leftRemove}leftRemove个左括号和rightRemove \textit{rightRemove}rightRemove个右括号得到有效的字符串。

得到左括号和右括号的最少删除次数之后，执行回溯，回溯过程中需要维护当前字符串str \textit{str}str、开始下标index \textit{index}index、左括号的剩余删除次数leftRemove \textit{leftRemove}leftRemove和右括号的剩余删除次数rightRemove \textit{rightRemove}rightRemove，回溯的做法如下。

• 如果leftRemove = rightRemove = 0 \textit{leftRemove} = \textit{rightRemove} = 0leftRemove=rightRemove=0，则所有的删除次数都用完，当str \textit{str}str有效时将str \textit{str}str添加到答案中。

• 如果leftRemove \textit{leftRemove}leftRemove和rightRemove \textit{rightRemove}rightRemove中至少有一个大于0 00，则需要继续删除括号。对于从index \textit{index}index开始的每个下标i ii，如果str [ i ] \textit{str}[i]str[i]是括号且对应的剩余删除次数大于0 00，则得到将str [ i ] \textit{str}[i]str[i]删除后的新字符串，将对应的剩余删除次数减1 11，从开始下标i ii继续回溯。

回溯过程中有以下两处可以剪枝。

1. 如果当前字符串的剩余字符个数少于leftRemove + rightRemove \textit{leftRemove} + \textit{rightRemove}leftRemove+rightRemove，则即使将剩余字符全部删除也不可能得到有效字符串，因此停止当前回溯。

2. 如果当前字符串中有两个相邻的相同括号字符，则删除其中任意一个括号字符得到的新字符串是相同的，因此只需要考虑删除其中一个括号字符得到的新字符串，跳过相邻的其余相同括号字符。

代码

classSolution{List<String>valid=newArrayList<String>();publicList<String>removeInvalidParentheses(Strings){intleftRemove=0,rightRemove=0;intlength=s.length();for(inti=0;i<length;i++){charc=s.charAt(i);if(c=='('){leftRemove++;}elseif(c==')'){if(leftRemove==0){rightRemove++;}else{leftRemove--;}}}backtrack(s,0,leftRemove,rightRemove);returnvalid;}publicvoidbacktrack(Stringstr,intindex,intleftRemove,intrightRemove){if(leftRemove==0&&rightRemove==0){if(isValid(str)){valid.add(str);}}else{intlength=str.length();for(inti=index;i<length;i++){if(length-i<leftRemove+rightRemove){break;}charc=str.charAt(i);if(i>index&&c==str.charAt(i-1)){continue;}StringnextStr=str.substring(0,i)+str.substring(i+1);if(c=='('&&leftRemove>0){backtrack(nextStr,i,leftRemove-1,rightRemove);}elseif(c==')'&&rightRemove>0){backtrack(nextStr,i,leftRemove,rightRemove-1);}}}}publicbooleanisValid(Stringstr){intcount=0;intlength=str.length();for(inti=0;i<length;i++){charc=str.charAt(i);if(c=='('){count++;}elseif(c==')'){count--;}if(count<0){returnfalse;}}returncount==0;}}

复杂度分析

• 时间复杂度：O ( n 2 × 2 n ) O(n^2 \times 2^n)O(n2×2n)，其中n nn是字符串s ss的长度。字符串s ss最多有2 n 2^n2n个子序列，因此回溯的过程中最多遍历2 n 2^n2n个不同的字符串，对于每个字符串的操作时间是O ( n 2 ) O(n^2)O(n2)的时间，将每个有效字符串添加到答案需要O ( n ) O(n)O(n)的时间，因此时间复杂度是O ( n 2 × 2 n ) O(n^2 \times 2^n)O(n2×2n)。

• 空间复杂度：O ( n × 2 n ) O(n \times 2^n)O(n×2n)，其中n nn是字符串s ss的长度。字符串s ss最多有2 n 2^n2n个子序列，因此回溯的过程中最多遍历2 n 2^n2n个不同的字符串，每个字符串的长度不超过n nn，因此空间复杂度是O ( n × 2 n ) O(n \times 2^n)O(n×2n)。