题目描述
282. Expression Add Operators
Given a string that contains only digits 0-9
and a target value, return all possibilities to add binary operators (not unary) +
, -
, or *
between the digits so they evaluate to the target value.
Example 1:
Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"]
Example 2:
Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]
Example 3:
Input: num = "105", target = 5
Output: ["1*0+5","10-5"]
Example 4:
Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]
Example 5:
Input: num = "3456237490", target = 9191
Output: []
题意:给定一个仅包含数字 0-9
的字符串和一个目标值,在数字之间添加二元运算符(不是一元)+
、-
或 *
,返回所有能够得到目标值的表达式。
算法1
(dfs) $O(4^n)$
题解:这题很适合使用dfs来求解,首先决定将字符串划分为哪些数字,然后这些数字之间可以插入+
,-
和*
。很自然的dfs就是当前遍历了多少个字符了,当前遍历过的表达式的值,当遍历完所有的字符并且当前表达式的长度为target
的时候记录答案。但是这里我们还需要注意的是,如果只有+
和-
,那么上述做法没问题,但是有了乘法之后,会改变运算符的优先级,所以我们需要保留当前表达式的最后一个运算结果是多少。如当前表达式为3 + 2 * 5
,我们应该把10 = 2 * 5
记录下来,以防止下一个运算符还是*
。另外需要注意的是前导0。综上所述,我们代码的整体思路如下:
dfs
函数的参数分别为:原始字符串num
,目标结果target
,当前需要遍历哪一个数字pos
,当前表达式exp
的长度len
,当前表达式的上一个结果prev
,当前表达式的值cur
。
res
记录答案,exp
字符串记录当前表达式,n
记录num
的长度。exp
的最大长度为2 * n - 1
,所以开一个2 * n
的数组就可以了。
- 当
pos = n
说明我们遍历完字符串了,如果当前表达式exp[0:len)
的值cur = target
,那么记录答案。 next
代表从pos
位置开始我们准备选取的下一个数字值是多少,s
记录当前遍历到num
的什么位置,l
记录当前字符串长度,也是表示下一个表达式字符应该放在什么地方。- 如果
s != 0
,说明s[l]
的位置需要放置一个运算符,+,-,*
,同时len ++
。 - 然后,我们依次遍历每一个可能的操作数,排除前导0和过于大的数。并且把这个数字放入
exp
中。 - 如果
s == 0
,说明当前数字是第一个数字,那么前面不需要运算符。 - 否则的话,我们在
exp[l]
的位置依次放入+,-,*
,同时修改相应的prev
和cur
的值。
时间复杂度分析:每个位置可以是+
,-
,*
,’ ‘四种可能,所以总的时间复杂度$O(4^n)$
class Solution {
public:
vector<string> res;
string exp;
int n;
vector<string> addOperators(string num, int target) {
n = num.length();
exp = string(n * 2,' ') ;
dfs(num,target,0,0,0,0);
return res;
}
void dfs(string &num,int target,int pos,int len,long prev,long cur)
{
if(pos == n)
{
if(cur == target) res.push_back(exp.substr(0,len));
return ;
}
long long next = 0;
int s = pos,l = len;
if(s != 0) ++len;
while(pos < n)
{
next = next * 10 + (num[pos] - '0');
if(num[s] == '0' && pos - s > 0) break;
if(next > INT_MAX) break;
exp[len ++] = num[pos ++];
if(s == 0)
{
dfs(num,target,pos,len,next,next);
continue;
}
exp[l] = '+';dfs(num,target,pos,len,next,cur + next);
exp[l] = '-';dfs(num,target,pos,len,-next,cur - next);
exp[l] = '*';dfs(num,target,pos,len,prev * next,cur - prev + prev * next);
}
}
};
和lz思路一样,发一个python版的
555