[Leetcode]306. Additive Number

Question

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:

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.

Solution

The idea is quiet basic.

1. Choose the first number A, it can be the leftmost 1 up to i digits. i<=(L-1)/2, because the third number should be at least as long as the first number.

2. Choose the second number B, it can be the leftmost 1 up to j digits excluding the first number. The limit for j is in 2 conditions:

   • if the length of second number( j - i ) is longer than the first number( i ), then the third number’s length( L - j ) should >= ( j - i ).

   • if the length of second number( j - i ) is shorter than or equals to the first number( i ), then the third number’s length( L - j ) should >= i .

3. Recursively check if there is one solution.

public class Solution {
    public boolean isAdditiveNumber(String num) {
        int L = num.length();
        
        for(int i = 1; i <= (L-1)/2 ; i++ ){  // Length of A is from 1 to (L-1)/2. 
            
            if( num.charAt(0) == '0' && i>=2 ) break;
            // Length of B is from 1 to L-(A+B),and L-(A+B) >= max(A,B)
            for( int j = i+1; (L-j) >= i && (L-j) >= j-i ; j++ ){ 
         
              if( num.charAt(i) == '0' && j-i>=2 ) break;      
              
              long A = Long.parseLong( num.substring(0,i) );
              long B = Long.parseLong( num.substring(i,j) );
              String substr = num.substring(j);
              
              if( isAdditive( substr , A, B) == true ) return true; 
            }
        }
        return false;
    }
    
    private boolean isAdditive(String str, long A,long B){
        if( str.equals("") ) return true;
        long sum = A + B;
        String sumStr = String.valueOf(sum);
        if( !str.startsWith(sumStr) ) return false;
        
        return isAdditive( str.substring(sumStr.length()), B, sum);
    }
}