文章目录题目标题和出处难度题目描述要求示例数据范围解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析题目标题和出处标题删除无效的括号出处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≤25s \texttt{s}s由小写英语字母以及括号‘(’ \texttt{(}‘(’和‘)’ \texttt{)}‘)’组成s \texttt{s}s中至多含20 \texttt{20}20个括号解法一思路和算法这道题要求从字符串s ss中删除最少数量的无效括号使得字符串中剩余的字符有效。最少操作符合广度优先搜索的应用场景因此可以使用广度优先搜索得到删除次数最少的情况下的全部有效字符串。广度优先搜索的做法是对于字符串中的每个括号将其删除之后得到一个新的字符串将新的字符串在下一轮搜索。第0 00轮遍历初始字符串s ss第i ii轮遍历所有删除i ii个括号之后的字符串即每一轮遍历的字符串的长度依次递减。对于当前轮的全部字符串判断每个字符串是否有效如果有效则将其添加到答案中。如果一轮结束之后答案不为空则找到删除次数最少的情况下的全部有效字符串此时结束搜索返回答案。实现方面有以下两点说明。如果当前字符串中有两个相邻的相同括号字符则删除其中任意一个括号字符得到的新字符串是相同的因此只需要考虑删除其中一个括号字符得到的新字符串跳过相邻的其余相同括号字符。使用哈希集合存储每一轮遍历的字符串可以确保同一个字符串只访问一次。代码classSolution{publicListStringremoveInvalidParentheses(Strings){ListStringvalidnewArrayListString();SetStringsetnewHashSetString();set.add(s);while(!set.isEmpty()){for(Stringstr:set){if(isValid(str)){valid.add(str);}}if(!valid.isEmpty()){break;}SetStringnextSetnewHashSetString();for(Stringstr:set){intlengthstr.length();for(inti0;ilength;i){charcstr.charAt(i);if((i0cstr.charAt(i-1))||(c!(c!))){continue;}StringnextStrstr.substring(0,i)str.substring(i1);nextSet.add(nextStr);}}setnextSet;}returnvalid;}publicbooleanisValid(Stringstr){intcount0;intlengthstr.length();for(inti0;ilength;i){charcstr.charAt(i);if(c(){count;}elseif(c)){count--;}if(count0){returnfalse;}}returncount0;}}复杂度分析时间复杂度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} 0leftRemove0时将rightRemove \textit{rightRemove}rightRemove加1 11当leftRemove 0 \textit{leftRemove} 0leftRemove0时将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} 0leftRemoverightRemove0则所有的删除次数都用完当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继续回溯。回溯过程中有以下两处可以剪枝。如果当前字符串的剩余字符个数少于leftRemove rightRemove \textit{leftRemove} \textit{rightRemove}leftRemoverightRemove则即使将剩余字符全部删除也不可能得到有效字符串因此停止当前回溯。如果当前字符串中有两个相邻的相同括号字符则删除其中任意一个括号字符得到的新字符串是相同的因此只需要考虑删除其中一个括号字符得到的新字符串跳过相邻的其余相同括号字符。代码classSolution{ListStringvalidnewArrayListString();publicListStringremoveInvalidParentheses(Strings){intleftRemove0,rightRemove0;intlengths.length();for(inti0;ilength;i){charcs.charAt(i);if(c(){leftRemove;}elseif(c)){if(leftRemove0){rightRemove;}else{leftRemove--;}}}backtrack(s,0,leftRemove,rightRemove);returnvalid;}publicvoidbacktrack(Stringstr,intindex,intleftRemove,intrightRemove){if(leftRemove0rightRemove0){if(isValid(str)){valid.add(str);}}else{intlengthstr.length();for(intiindex;ilength;i){if(length-ileftRemoverightRemove){break;}charcstr.charAt(i);if(iindexcstr.charAt(i-1)){continue;}StringnextStrstr.substring(0,i)str.substring(i1);if(c(leftRemove0){backtrack(nextStr,i,leftRemove-1,rightRemove);}elseif(c)rightRemove0){backtrack(nextStr,i,leftRemove,rightRemove-1);}}}}publicbooleanisValid(Stringstr){intcount0;intlengthstr.length();for(inti0;ilength;i){charcstr.charAt(i);if(c(){count;}elseif(c)){count--;}if(count0){returnfalse;}}returncount0;}}复杂度分析时间复杂度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)。
