Skip to content

Commit 99c4dd1

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0282.Expression Add Operators
1 parent 4adaba2 commit 99c4dd1

File tree

4 files changed

+169
-2
lines changed

4 files changed

+169
-2
lines changed

‎solution/0200-0299/0282.Expression Add Operators/README.md

Lines changed: 56 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -63,7 +63,29 @@
6363
<!-- 这里可写当前语言的特殊实现逻辑 -->
6464

6565
```python
66-
66+
class Solution:
67+
def addOperators(self, num: str, target: int) -> List[str]:
68+
ans = []
69+
70+
def dfs(u, prev, curr, path):
71+
if u == len(num):
72+
if curr == target:
73+
ans.append(path)
74+
return
75+
for i in range(u, len(num)):
76+
if i != u and num[u] == '0':
77+
break
78+
next = int(num[u: i+1])
79+
if u == 0:
80+
dfs(i + 1, next, next, path + str(next))
81+
else:
82+
dfs(i + 1, next, curr + next, path + "+" + str(next))
83+
dfs(i + 1, -next, curr - next, path + "-" + str(next))
84+
dfs(i + 1, prev * next, curr - prev +
85+
prev * next, path + "*" + str(next))
86+
87+
dfs(0, 0, 0, "")
88+
return ans
6789
```
6890

6991
### **Java**
@@ -72,6 +94,39 @@
7294

7395
```java
7496

97+
class Solution {
98+
private List<String> ans;
99+
private String num;
100+
private int target;
101+
102+
public List<String> addOperators(String num, int target) {
103+
ans = new ArrayList<>();
104+
this.num = num;
105+
this.target = target;
106+
dfs(0, 0, 0, "");
107+
return ans;
108+
}
109+
110+
private void dfs(int u, long prev, long curr, String path) {
111+
if (u == num.length()) {
112+
if (curr == target) ans.add(path);
113+
return ;
114+
}
115+
for (int i = u; i < num.length(); i++) {
116+
if (i != u && num.charAt(u) == '0') {
117+
break;
118+
}
119+
long next = Long.parseLong(num.substring(u, i + 1));
120+
if (u == 0) {
121+
dfs(i + 1, next, next, path + next);
122+
} else {
123+
dfs(i + 1, next, curr + next, path + "+" + next);
124+
dfs(i + 1, -next, curr - next, path + "-" + next);
125+
dfs(i + 1, prev * next, curr - prev + prev * next, path + "*" + next);
126+
}
127+
}
128+
}
129+
}
75130
```
76131

77132
### **...**

‎solution/0200-0299/0282.Expression Add Operators/README_EN.md

Lines changed: 56 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,13 +40,68 @@
4040
### **Python3**
4141

4242
```python
43-
43+
class Solution:
44+
def addOperators(self, num: str, target: int) -> List[str]:
45+
ans = []
46+
47+
def dfs(u, prev, curr, path):
48+
if u == len(num):
49+
if curr == target:
50+
ans.append(path)
51+
return
52+
for i in range(u, len(num)):
53+
if i != u and num[u] == '0':
54+
break
55+
next = int(num[u: i+1])
56+
if u == 0:
57+
dfs(i + 1, next, next, path + str(next))
58+
else:
59+
dfs(i + 1, next, curr + next, path + "+" + str(next))
60+
dfs(i + 1, -next, curr - next, path + "-" + str(next))
61+
dfs(i + 1, prev * next, curr - prev +
62+
prev * next, path + "*" + str(next))
63+
64+
dfs(0, 0, 0, "")
65+
return ans
4466
```
4567

4668
### **Java**
4769

4870
```java
4971

72+
class Solution {
73+
private List<String> ans;
74+
private String num;
75+
private int target;
76+
77+
public List<String> addOperators(String num, int target) {
78+
ans = new ArrayList<>();
79+
this.num = num;
80+
this.target = target;
81+
dfs(0, 0, 0, "");
82+
return ans;
83+
}
84+
85+
private void dfs(int u, long prev, long curr, String path) {
86+
if (u == num.length()) {
87+
if (curr == target) ans.add(path);
88+
return ;
89+
}
90+
for (int i = u; i < num.length(); i++) {
91+
if (i != u && num.charAt(u) == '0') {
92+
break;
93+
}
94+
long next = Long.parseLong(num.substring(u, i + 1));
95+
if (u == 0) {
96+
dfs(i + 1, next, next, path + next);
97+
} else {
98+
dfs(i + 1, next, curr + next, path + "+" + next);
99+
dfs(i + 1, -next, curr - next, path + "-" + next);
100+
dfs(i + 1, prev * next, curr - prev + prev * next, path + "*" + next);
101+
}
102+
}
103+
}
104+
}
50105
```
51106

52107
### **...**

‎solution/0200-0299/0282.Expression Add Operators/Solution.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
2+
class Solution {
3+
private List<String> ans;
4+
private String num;
5+
private int target;
6+
7+
public List<String> addOperators(String num, int target) {
8+
ans = new ArrayList<>();
9+
this.num = num;
10+
this.target = target;
11+
dfs(0, 0, 0, "");
12+
return ans;
13+
}
14+
15+
private void dfs(int u, long prev, long curr, String path) {
16+
if (u == num.length()) {
17+
if (curr == target) ans.add(path);
18+
return ;
19+
}
20+
for (int i = u; i < num.length(); i++) {
21+
if (i != u && num.charAt(u) == '0') {
22+
break;
23+
}
24+
long next = Long.parseLong(num.substring(u, i + 1));
25+
if (u == 0) {
26+
dfs(i + 1, next, next, path + next);
27+
} else {
28+
dfs(i + 1, next, curr + next, path + "+" + next);
29+
dfs(i + 1, -next, curr - next, path + "-" + next);
30+
dfs(i + 1, prev * next, curr - prev + prev * next, path + "*" + next);
31+
}
32+
}
33+
}
34+
}

‎solution/0200-0299/0282.Expression Add Operators/Solution.py

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
class Solution:
2+
def addOperators(self, num: str, target: int) -> List[str]:
3+
ans = []
4+
5+
def dfs(u, prev, curr, path):
6+
if u == len(num):
7+
if curr == target:
8+
ans.append(path)
9+
return
10+
for i in range(u, len(num)):
11+
if i != u and num[u] == '0':
12+
break
13+
next = int(num[u: i+1])
14+
if u == 0:
15+
dfs(i + 1, next, next, path + str(next))
16+
else:
17+
dfs(i + 1, next, curr + next, path + "+" + str(next))
18+
dfs(i + 1, -next, curr - next, path + "-" + str(next))
19+
dfs(i + 1, prev * next, curr - prev +
20+
prev * next, path + "*" + str(next))
21+
22+
dfs(0, 0, 0, "")
23+
return ans

0 commit comments

Comments
 (0)