问题：
Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
For example:
"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.
Follow up:
How would you handle overflow for very large input integers?解决：
① 递归方法。使用BigInteger表示数字，从而避免溢出。
如果x1的长度是 i , x2的长度是 j，那么它们的和的长度应该至少是Math.max（i，j）。左边序列的长度减去x1和x2的长度为n-i-j。
import java.math.BigInteger;
class Solution { public boolean isAdditiveNumber(String num) { int len = num.length(); for (int i = 1;i <= len / 2;i ++){ if (num.charAt(0) == '0' && i > 1) return false; BigInteger x1 = new BigInteger(num.substring(0,i)); for (int j = 1;Math.max(i,j) <= len - i - j;j ++){ if (num.charAt(i) == '0' && j > 1) break; BigInteger x2 = new BigInteger(num.substring(i,i + j)); if (isValid(x1,x2,i + j,num)){ return true; } } } return false; } public boolean isValid(BigInteger x1,BigInteger x2,int start,String num){ if (start == num.length()) return true; x2 = x2.add(x1); x1 = x2.subtract(x1); String sum = x2.toString(); return num.startsWith(sum,start) && isValid(x1,x2,start + sum.length(),num); } }② 非递归方法。
import java.math.BigInteger;
class Solution { //9ms public boolean isAdditiveNumber(String num) { int len = num.length(); for (int i = 1;i <= len / 2;i ++){ for (int j = 1;Math.max(i,j) <= len - i - j;j ++){ if (isValid(i,j,num)){ return true; } } } return false; } public 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; } }③ 如果没有溢出，可以考虑使用更快的Long。
class Solution { //3ms
public boolean isAdditiveNumber(String num) { int n = num.length(); for (int i = 1; i <= n / 2; i ++) for (int j = 1; Math.max(j, i) <= 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; Long x1 = Long.parseLong(num.substring(0, i)); Long x2 = Long.parseLong(num.substring(i, i + j)); for (int start = i + j; start != num.length(); start += sum.length()) { x2 = x2 + x1; x1 = x2 - x1; sum = x2.toString(); if (!num.startsWith(sum, start)) return false; } return true; } }④ 在discuss中看到的。
class Solution { 0ms
public boolean isAdditiveNumber(String num) { if(num.length() == 0) return false; return helper(num, 0, 0, 0, 0); } private boolean helper(String num, int index, int first, int second, int count) { if(index == num.length()) return count >= 3; int n = 0; for(; index < num.length(); index++) { n = n * 10 + num.charAt(index) - '0'; if(count >= 2) { if(first + second == n) { index++; break; } }else{ if(helper(num, index+1, second, n, count+1)) return true; } if(n == 0) return false; } if(first + second == n) return helper(num, index, second, n, count+1); return false; } }