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
| class Solution {
public boolean isAdditiveNumber(String num) {
return search(num, 0);
}
private boolean search(String num, int firstStart) {
for (int firstEnd = firstStart; firstEnd < num.length(); firstEnd++) {
if (firstEnd - firstStart + 1 > num.length() - firstEnd - 1) {
break;
}
int secondStart = firstEnd + 1;
for (int secondEnd = secondStart; secondEnd < num.length(); secondEnd++) {
if (secondEnd - secondStart + 1 > num.length() - secondEnd - 1 || firstEnd - firstStart + 1 > num.length() - secondEnd - 1) {
break;
}
if (num.charAt(secondStart) == '0' && secondEnd > secondStart) {
break;
}
int thirdStart = secondEnd + 1;
for (int thirdEnd = thirdStart; thirdEnd < num.length(); thirdEnd++) {
if (num.charAt(thirdStart) == '0' && thirdEnd > thirdStart) {
break;
}
int temp = compare(num, firstStart, firstEnd, secondStart, secondEnd, thirdStart, thirdEnd);
if (temp < 0) {
break;
}
if (temp > 0) {
continue;
}
if (thirdEnd == num.length() - 1) {
return true;
}
if (search(num, secondStart)) {
return true;
}
}
}
}
return false;
}
private int compare(String num, int firstStart, int firstEnd, int secondStart, int secondEnd, int thirdStart, int thirdEnd) {
String str = add(num, firstStart, firstEnd, secondStart, secondEnd);
return compare(str, num, thirdStart, thirdEnd);
}
private int compare(String str, String num, int thirdStart, int thirdEnd) {
int thirdLength = thirdEnd - thirdStart + 1;
if (str.length() < thirdLength) {
return -1;
}
if (str.length() > thirdLength) {
return 1;
}
for (int i = 0; i < thirdLength; i++) {
if (str.charAt(i) == num.charAt(thirdStart + i)) {
continue;
}
return str.charAt(i) - num.charAt(thirdStart + i);
}
return 0;
}
private String add(String num, int firstStart, int firstEnd, int secondStart, int secondEnd) {
StringBuilder sb = new StringBuilder();
int i = firstEnd;
int j = secondEnd;
int carry = 0;
while (i >= firstStart && j >= secondStart) {
int temp = carry + num.charAt(i) - '0' + num.charAt(j) - '0';
sb.append(temp % 10);
carry = temp / 10;
i--;
j--;
}
for (int k = i; k >= firstStart; k--) {
int temp = carry + num.charAt(k) - '0';
sb.append(temp % 10);
carry = temp / 10;
}
for (int k = j; k >= secondStart; k--) {
int temp = carry + num.charAt(k) - '0';
sb.append(temp % 10);
carry = temp / 10;
}
if (carry > 0) {
sb.append(carry);
}
return sb.reverse().toString();
}
}
|