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
| class Solution {
String num;
int n;
List<List<Integer>> list = new ArrayList<>();
public boolean isAdditiveNumber(String num) {
this.num = num;
n = num.length();
return dfs(0);
}
private boolean dfs(int u) {
int m = list.size();
if (u == n) return m >= 3;
int max = num.charAt(u) == '0' ? u + 1 : n;
List<Integer> cur = new ArrayList<>();
for (int i = u; i < max; i++) {
cur.add(0, num.charAt(i) - '0');
if (m < 2 || check(list.get(m - 2), list.get(m - 1), cur)) {
list.add(cur);
if (dfs(i + 1)) return true;
list.remove(list.size() - 1);
}
}
return false;
}
private boolean check(List<Integer> a, List<Integer> b, List<Integer> c) {
List<Integer> ans = new ArrayList<>();
int t = 0;
for (int i = 0; i < a.size() || i < b.size(); ++i) {
if (i < a.size()) t += a.get(i);
if (i < b.size()) t += b.get(i);
ans.add(t % 10);
t /= 10;
}
if (t > 0) ans.add(t);
boolean ok = c.size() == ans.size();
for (int i = 0; i < c.size() && ok; ++i) {
if (!c.get(i).equals(ans.get(i))) {
ok = false;
break;
}
}
return ok;
}
}
|
wechat
