My code:
import java.math.BigInteger;
public class Solution {
public boolean isAdditiveNumber(String num) {
int n = num.length();
for (int i = 1; i <= n / 2; i++) {
for (int j = 1; Math.max(i, j) <= n - i - j; j++) {
if (isValid(i, j, num)) {
return true;
}
}
}
return false;
}
private boolean isValid(int i, int j, String num) {
if (num.charAt(0) == '0' && i > 1) {
return false;
}
if (num.charAt(i) == '0' && j > 1) {
return false;
}
String sum = "";
BigInteger x1 = new BigInteger(num.substring(0, i));
BigInteger x2 = new BigInteger(num.substring(i, i + j));
for (int start = i + j; start != num.length(); start += sum.length()) {
x2 = x2.add(x1);
x1 = x2.subtract(x1);
sum = x2.toString();
if (!num.startsWith(sum, start)) {
return false;
}
}
return true;
}
}
reference:
https://discuss.leetcode.com/topic/29856/java-recursive-and-iterative-solutions
解释的很好。
Anyway, Good luck, Richardo! -- 10/14/2016
