题目描述
给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回 所有 能够得到 target 的表达式。
注意，返回表达式中的操作数 不应该 包含前导零。
示例 1:
输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"]
解释: “1*2*3” 和 “1+2+3” 的值都是6。
示例 2:
输入: num = "232", target = 8
输出: ["2*3+2", "2+3*2"]
解释: “2*3+2” 和 “2+3*2” 的值都是8。
示例 3:
输入: num = "3456237490", target = 9191
输出: []
解释: 表达式 “3456237490” 无法得到 9191 。
提示：
1 <= num.length <= 10num 仅含数字-231 <= target <= 231 - 1
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
ans = []
def dfs(u, prev, curr, path):
if u == len(num):
if curr == target:
ans.append(path)
return
for i in range(u, len(num)):
if i != u and num[u] == '0':
break
next = int(num[u : i + 1])
if u == 0:
dfs(i + 1, next, next, path + str(next))
else:
dfs(i + 1, next, curr + next, path + "+" + str(next))
dfs(i + 1, -next, curr - next, path + "-" + str(next))
dfs(
i + 1,
prev * next,
curr - prev + prev * next,
path + "*" + str(next),
)
dfs(0, 0, 0, "")
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | class Solution {
private List<String> ans;
private String num;
private int target;
public List<String> addOperators(String num, int target) {
ans = new ArrayList<>();
this.num = num;
this.target = target;
dfs(0, 0, 0, "");
return ans;
}
private void dfs(int u, long prev, long curr, String path) {
if (u == num.length()) {
if (curr == target) ans.add(path);
return;
}
for (int i = u; i < num.length(); i++) {
if (i != u && num.charAt(u) == '0') {
break;
}
long next = Long.parseLong(num.substring(u, i + 1));
if (u == 0) {
dfs(i + 1, next, next, path + next);
} else {
dfs(i + 1, next, curr + next, path + "+" + next);
dfs(i + 1, -next, curr - next, path + "-" + next);
dfs(i + 1, prev * next, curr - prev + prev * next, path + "*" + next);
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109 | using System;
using System.Collections.Generic;
public class Expression
{
public long Value;
public override string ToString()
{
return Value.ToString();
}
}
public class BinaryExpression : Expression
{
public char Operator;
public Expression LeftChild;
public Expression RightChild;
public override string ToString()
{
return string.Format("{0}{1}{2}", LeftChild, Operator, RightChild);
}
}
public class Solution {
public IList<string> AddOperators(string num, int target) {
var results = new List<string>();
if (string.IsNullOrEmpty(num)) return results;
this.num = num;
this.results = new List<Expression>[num.Length, num.Length, 3];
foreach (var ex in Search(0, num.Length - 1, 0))
{
if (ex.Value == target)
{
results.Add(ex.ToString());
}
}
return results;
}
private string num;
private List<Expression>[,,] results;
private List<Expression> Search(int left, int right, int level)
{
if (results[left, right, level] != null)
{
return results[left, right, level];
}
var result = new List<Expression>();
if (level < 2)
{
for (var i = left + 1; i <= right; ++i)
{
List<Expression> leftResult, rightResult;
leftResult = Search(left, i - 1, level);
rightResult = Search(i, right, level + 1);
foreach (var l in leftResult)
{
foreach (var r in rightResult)
{
var newObjects = new List<Tuple<char, long>>();
if (level == 0)
{
newObjects.Add(Tuple.Create('+', l.Value + r.Value));
newObjects.Add(Tuple.Create('-', l.Value - r.Value));
}
else
{
newObjects.Add(Tuple.Create('*', l.Value * r.Value));
}
foreach (var newObject in newObjects)
{
result.Add(new BinaryExpression
{
Value = newObject.Item2,
Operator = newObject.Item1,
LeftChild = l,
RightChild = r
});
}
}
}
}
}
else
{
if (left == right || num[left] != '0')
{
long x = 0;
for (var i = left; i <= right; ++i)
{
x = x * 10 + num[i] - '0';
}
result.Add(new Expression
{
Value = x
});
}
}
if (level < 2)
{
result.AddRange(Search(left, right, level + 1));
}
return results[left, right, level] = result;
}
}
|