回溯题目：给表达式添加运算符

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题给表达式添加运算符出处282. 给表达式添加运算符难度8 级题目描述要求给定一个仅包含数字的字符串num \texttt{num}num和一个整数target \texttt{target}target可以在num \texttt{num}num的数字之间添加二元运算符‘’ \texttt{}‘’、‘-’ \texttt{-}‘-’和‘*’ \texttt{*}‘*’返回所有能够得到target \texttt{target}target的表达式。返回的表达式中的操作数不应该包含前导零。示例示例 1输入num 123, target 6 \texttt{num 123, target 6}num 123, target 6输出[123, 1*2*3] \texttt{[123, 1*2*3]}[123, 1*2*3]解释1*2*3 \texttt{1*2*3}1*2*3和123 \texttt{123}123的值都是6 \texttt{6}6。示例 2输入num 232, target 8 \texttt{num 232, target 8}num 232, target 8输出[2*32, 23*2] \texttt{[2*32, 23*2]}[2*32, 23*2]解释2*32 \texttt{2*32}2*32和23*2 \texttt{23*2}23*2的值都是8 \texttt{8}8。示例 3输入num 3456237490, target 9191 \texttt{num 3456237490, target 9191}num 3456237490, target 9191输出[] \texttt{[]}[]解释无法从3456237490 \texttt{3456237490}3456237490创建表达式得到9191 \texttt{9191}9191。数据范围1 ≤ num.length ≤ 10 \texttt{1} \le \texttt{num.length} \le \texttt{10}1≤num.length≤10num \texttt{num}num仅含数字-2 31 ≤ target ≤ 2 31 − 1 \texttt{-2}^\texttt{31} \le \texttt{target} \le \texttt{2}^\texttt{31} - \texttt{1}-231≤target≤231−1解法思路和算法用n nn表示字符串nums \textit{nums}nums的长度。由于每个二元运算符必须位于两个数字之间因此有n − 1 n - 1n−1个位置可以插入二元运算符每个位置可以插入3 33种二元运算符之一或不插入二元运算符因此每个位置有4 44种选择可能的表达式有4 n − 1 4^{n - 1}4n−1个。为了得到所有符合要求的表达式需要使用回溯遍历所有可能的表达式。如果表达式中的操作数不含前导零且表达式的计算结果等于target \textit{target}target则该表达式是符合要求的表达式。直观的做法是每次生成一个表达式之后遍历表达式并判断是否符合要求该做法需要对每个可能的表达式使用O ( n ) O(n)O(n)的时间判断是否符合要求时间复杂度较高。另一种做法是在生成表达式的过程中确保所有的操作数都不含前导零并维护表达式的计算结果当表达式生成结束时即可确保所有的操作数都不含前导零并知道表达式的计算结果不需要再次遍历表达式判断是否符合要求。由于乘法的优先级高于加法和减法为了在生成表达式的过程中维护表达式的计算结果需要在回溯的过程中维护当前遍历到的下标index \textit{index}index、当前遍历到的部分的中间结果result \textit{result}result和被乘数multiplicand \textit{multiplicand}multiplicand。回溯的终止条件是index n \textit{index} nindexn此时生成完整的表达式如果result target \textit{result} \textit{target}resulttarget则将表达式添加到答案中。当index n \textit{index} nindexn时回溯操作如下。记exprLength \textit{exprLength}exprLength为当前表达式的长度。如果index 0 \textit{index} 0index0则当前位置不是表达式的起始位置需要在表达式的下标exprLength \textit{exprLength}exprLength处插入一个运算符因此在表达式的末尾即下标exprLength \textit{exprLength}exprLength处添加一个空格作为占位符。如果index 0 \textit{index} 0index0则当前位置是表达式的起始位置不在表达式的下标exprLength \textit{exprLength}exprLength处插入运算符因此不添加占位符。用end \textit{end}end表示从下标index \textit{index}index开始的操作数的最大结束下标需要遵循操作数不能有前导零的规则。如果num [ index ] \textit{num}[\textit{index}]num[index]为0 00则end index \textit{end} \textit{index}endindex如果num [ index ] \textit{num}[\textit{index}]num[index]不为0 00则end n − 1 \textit{end} n - 1endn−1。从左到右遍历范围[ index , end ] [\textit{index}, \textit{end}][index,end]中的每个下标i ii用curr \textit{curr}curr表示字符串num \textit{num}num的下标范围[ index , i ] [\textit{index}, i][index,i]的子串表示的数字即当前操作数。将curr \textit{curr}curr添加到表达式的末尾然后执行如下操作。如果index 0 \textit{index} 0index0则没有插入任何运算符使用下标i 1 i 1i1、中间结果curr \textit{curr}curr和被乘数curr \textit{curr}curr继续回溯。如果index 0 \textit{index} 0index0则需要依次将加号、减号和乘号填到占位符的位置并分别回溯。对于加号使用下标i 1 i 1i1、中间结果result curr \textit{result} \textit{curr}resultcurr和被乘数curr \textit{curr}curr继续回溯。对于减号使用下标i 1 i 1i1、中间结果result − curr \textit{result} - \textit{curr}result−curr和被乘数− curr -\textit{curr}−curr继续回溯。对于乘号需要考虑到运算符优先级对中间结果和被乘数的影响因此使用下标i 1 i 1i1、中间结果result multiplicand × ( curr − 1 ) \textit{result} \textit{multiplicand} \times (\textit{curr} - 1)resultmultiplicand×(curr−1)和被乘数multiplicand × curr \textit{multiplicand} \times \textit{curr}multiplicand×curr继续回溯。范围[ index , end ] [\textit{index}, \textit{end}][index,end]中的所有下标遍历结束之后将表达式的长度设为exprLength \textit{exprLength}exprLength恢复到添加运算符占位符和当前操作数之前的状态。回溯结束时即可得到所有符合要求的表达式。代码classSolution{staticchar[]ops{,-,*};staticfinalintOPS_COUNTops.length;ListStringexpressionsnewArrayListString();intn;Stringnum;inttarget;StringBuffertempnewStringBuffer();publicListStringaddOperators(Stringnum,inttarget){this.nnum.length();this.numnum;this.targettarget;backtrack(0,0,0);returnexpressions;}publicvoidbacktrack(intindex,longresult,longmultiplicand){if(indexn){if(resulttarget){expressions.add(temp.toString());}}else{intexprLengthtemp.length();if(index0){temp.append( );}intendnum.charAt(index)0?index:n-1;longcurr0;for(intiindex;iend;i){intdigitnum.charAt(i)-0;currcurr*10digit;temp.append(digit);if(index0){backtrack(i1,curr,curr);}else{long[]nextResults{resultcurr,result-curr,resultmultiplicand*(curr-1)};long[]nextMultiples{curr,-curr,multiplicand*curr};for(intj0;jOPS_COUNT;j){temp.setCharAt(exprLength,ops[j]);backtrack(i1,nextResults[j],nextMultiples[j]);}}}temp.setLength(exprLength);}}}复杂度分析时间复杂度O ( 4 n ) O(4^n)O(4n)其中n nn是字符串nums \textit{nums}nums的长度。可能的表达式有4 n − 1 4^{n - 1}4n−1个对于每个符合要求的表达式需要O ( n ) O(n)O(n)的时间添加到答案中由于符合要求的表达式远少于4 n − 1 4^{n - 1}4n−1因此时间复杂度是O ( 4 n ) O(4^n)O(4n)。空间复杂度O ( n ) O(n)O(n)其中n nn是字符串nums \textit{nums}nums的长度。存储当前表达式的临时字符串和递归调用栈需要O ( n ) O(n)O(n)的空间。注意返回值不计入空间复杂度。