# Java Accepted 1ms, no BigInteger or Long needed.

• The idea is to choose i, j, k as the beginning of three string s1, s2, s3. If we see any combination s1 + s2 == s3, we move forward and compare s2 + s3 with s4 (the next possible number). i is 0 at first.

``````public class Solution {
if (num == null) return false;
int n = num.length();
if (n == 0) return false;
int half = (n - 1) >> 1;
for (int j = 1; j <= half; j++) {
for (int k = j + 1; k <= n - j && k + k <= n + j; k++) {
if (dfs(num, 0, j, k))
return true;
}
}
return false;
}
boolean dfs(String s, int i, int j, int k) {
if (k == s.length()) return true;
if (k > s.length()) return false;
if (s.charAt(i) == '0' && j > i + 1) return false;
if (s.charAt(j) == '0' && k > j + 1) return false;
if (s.charAt(k) == '0') return false;
String s1 = s.substring(i, j);
String s2 = s.substring(j, k);
int maxLen = Math.max(j-i, k-j);
if (k + maxLen > s.length())
return false;
String s3 = s.substring(k, k + maxLen);
if (equals(s1, s2, s3)) {
return dfs(s, j, k, k + maxLen);
}
if (k + maxLen + 1 > s.length())
return false;
String s4 = s.substring(k, k + maxLen + 1);
if (equals(s1, s2, s4)) {
return dfs(s, j, k, k + maxLen + 1);
} else
return false;
}
boolean equals(String s1, String s2, String s3) {
char[] w1 = s1.toCharArray();
char[] w2 = s2.toCharArray();
char[] w3 = s3.toCharArray();
int len1 = w1.length, len2 = w2.length, len3 = w3.length;
if (len3 < Math.max(len1, len2)) return false;
if (len3 > Math.max(len1, len2) + 1) return false;
if (len1 < len2) {
char[] temp = w2;
w2 = w1;
w1 = temp;
int temp2 = len1;
len1 = len2;
len2 = temp2;
}
int i;
int carry = 0;
for(i = 0; i < len2; i++) {
int sum = w1[len1 - i - 1] - '0' + w2[len2 - i - 1] - '0' + carry;
if (sum < 10) {
if (sum != w3[len3 - i - 1] - '0')
return false;
carry = 0;
} else {
sum = sum - 10;
carry = 1;
if (sum != w3[len3 - i - 1] - '0')
return false;
}
}
for (; i < len1; i++) {
int sum = w1[len1 - 1 - i] - '0'+ carry;
if (sum < 10) {
if (sum != w3[len3 - 1 - i] - '0')
return false;
carry = 0;
} else {
sum -= 10;
carry = 1;
if (sum != w3[len3 - 1 - i] - '0')
return false;
}
}
if (len1 == len3) {
if (carry  == 1) return false;
} else {
if (carry != w3[len3 - 1 - i] - '0')
return false;
}
return true;
}
}``````

• So what will happen to 112233?

In your idea you will find 1+1=2 first then return false.

But the correct answer is 11+22=33.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.