KK's blog

每天积累多一些

0%

LeetCode 282 Expression Add Operators

Posted on Edited on Disqus:

LeetCode

<div>

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Example 1:

<pre>Input: num = "123", target = 6 Output: ["123","1+2+3"] Explanation: Both "123" and "1+2+3" evaluate to 6. </pre>

Example 2:

<pre>Input: num = "232", target = 8 Output: ["23+2","2+32"] Explanation: Both "23+2" and "2+32" evaluate to 8. </pre>

Example 3:

<pre>Input: num = "3456237490", target = 9191 Output: [] Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191. </pre>

Constraints:

  • 1 <= num.length <= 10
  • num consists of only digits.
  • -2<sup>31</sup> <= target <= 2<sup>31</sup> - 1

</div>

题目大意：

求一串数字加入加减乘能得到target的所有可能性

解题思路：

求所有可能用DFS。属于分割型DFS，在数位之间加符号，数位可以是1个到多个。
一轮递归分割出符号 + 数字 另一种选择是数字 + 符号，但需要额外变量sign，因为不能立刻计算到结果。也不符合正常逻辑。所以选择前者。

由于运算都是二元，也就是用上述分割法，第一个数要特别处理。所以DFS中要特别处理第一个数。这样可以开始写加减。引入prev_res作为DFS参数，这样只要prev_res 加减 该轮数字即可得到该轮结果。用DFS模板5个标准参数外加prev_res： 

1
def dfs(self, num, st, target, prev_res, path, res):
这样只处理加减的DFS比较容易实现

最大难点在于乘法，参考LeetCode 227 Basic Calculator II，加减和乘除属于两层计算需要分别处理，所以引入新参数prev_multi_res，用于保存乘法结果，而刚才的命名为prev_add_res保存加减乘的全部结果

1
def dfs(self, num, st, target, prev_add_res, prev_multi_res, path, res):
举例2+3*4，按照原来的逻辑会计算到2+3=5，但此时如果遇到乘号，就要重新计算加法结果，先减去乘法结果，退回到2，再计算3*4=12这是乘法结果，再加回2得到新加法结果。进一步理解prev_multi_res，如果该轮是加减法，仍要将该轮的数作为prev_multi_res传到下轮DFS，因为如果下一轮是乘法，它就是第一个乘法的数。

解题步骤：

  1. 先实现加减法
  2. 再实现乘法

注意事项：

  1. 分割型DFS，选择每轮递归分割符号 + 数字。由于运算都是二元，特别处理第一个数
  2. 引入参数prev_add_res, prev_multi_res. prev_multi_res若是加减，用(+/-)cur_num, 否则用乘法结果prev_multi_res * cur_num。注意若是减法cur_num用负号
  3. 分割时数字不能有前缀0
  4. prev_res不用恢复状态因为是标量

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def addOperators(self, num: str, target: int) -> List[str]:
	res = []
	self.dfs(num, 0, target, 0, 0, '', res)
	return res

def dfs(self, num, st, target, prev_add_res, prev_multi_res, path, res):
	if st == len(num):
		if target == prev_add_res:
			res.append(path)
		return
	for i in range(st, len(num)):
		if i > st and num[st] == '0': # remember
			continue
		cur_num = int(num[st:i + 1])
		if not path: # remember
		    # first number, same as + case
			self.dfs(num, i + 1, target, prev_add_res + cur_num, cur_num, str(cur_num), res)
		else:
			self.dfs(num, i + 1, target, prev_add_res + cur_num, cur_num, path + '+' + str(cur_num), res) # use cur_num rather than cur
			self.dfs(num, i + 1, target, prev_add_res - cur_num, -cur_num, path + '-' + str(cur_num), res) # -cur_num rather than cur_num
			self.dfs(num, i + 1, target, (prev_add_res - prev_multi_res) + prev_multi_res * cur_num, prev_multi_res * cur_num, path + '*' + str(cur_num), res) # prev_multi_res * cur_num not cur_num

算法分析：

时间复杂度为<code>O(4<sup>n</sup>)</code>，空间复杂度O(n), 因为每个字符之间都有不加操作符，加3个操作符，所以是4，有n-1个间隔

Free mock interview