[LeetCode 306] Additive Number (

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.

Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: "112358"
Output: true 
Explanation: 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

Example 2:

Input: "199100199"
Output: true 
Explanation: The additive sequence is: 1, 99, 100, 199. 
             1 + 99 = 100, 99 + 100 = 199

Follow up:

• How would you handle overflow for very large input integers?

Solution

1. 首先，题目要求至少包含3个数，所以当str长度小于3时，直接返回false

2. 用2个loop来找尝试找first number & second number，第二个loop尝试找到second number以后，recursively找 这个first & second number, 和后面的数可以构成additive number。构成则返回true， 否则继续在loop中查找。

3. 在第一个loop找first number时，如果不是起始index 且 num.charAt (0) == '0', 说明当前数是类似 03，04 这种以0开始的数，不允许出现直接返回false。

4. 在第二个loop中，因为第三个数字的长度，必须大于first or second的长度， 所以for (int j = 1; num.length () - i -j >= Math.max (i, j); j++)

   • 此时，如果当前字符为0，且index不是起始，说明第二个数也是类似03，04这种数，但此时不返回false，而是需要继续loop循环。仅仅需要从第二个loop中break即可

5. Recursion找AdditiveNumber：

   • Arguments: FirstNumber, SecondNumber, 3rdStartIndex, String number
   • Base Case:
     if (thirdStartIndex == num.length ()) { return true; }
   • 求出3rd Number,
   • 如果num.startsWith (rd Number, thirdStartIndex) 则继续recursion求解。

class Solution {
    public boolean isAdditiveNumber(String num) {
        if (num == null || num.length () < 3) {
            return false;
        }
        
        // two loop, first loop ===> get first number
        // second loop ==> get second number
        
        // 第一个数字的长度只可能是整个字符串的一半，因为第三个数字的长度，至少是 first or second 的长度或更长
        for (int i = 1; i <= num.length () / 2; i++) {
            // i 不是起点，且当前index 为0， 直接return false，因为永远不可能避开 以0 开始
            if (num.charAt (0) == '0' && i > 1) {
                return false;
            }
            
            Long firstNumber = Long.valueOf (num.substring (0, i));
            
            // 第三个数字的长度，必须大于first or second的长度
            for (int j = 1; num.length () - i -j >= Math.max (i, j); j++) {
                if (num.charAt (i) == '0' && j > 1) {
                    break;  // break from 2nd loop, and continue first loop to try the remainning
                }
                
                Long secondNumber = Long.valueOf (num.substring (i, i + j));
                
                // recursively check if it is an additive number
                if (isAdditiveNumberHelper (firstNumber, secondNumber, i + j, num)) // the 3rd number startIndex
                    return true;
            }
        }
        
        return false;
    }
    
    public boolean isAdditiveNumberHelper (Long first, Long second, int thirdStartIndex, String num) {
        if (thirdStartIndex == num.length ()) {
            return true;
        }
        
        second = second + first; // 3rd 
        first = second - first;  // 2nd
        
        String sum = second.toString ();
        
        // 第三个数起始是不是符合预期？ 如果是继续迭代判断
        return num.startsWith (sum, thirdStartIndex) && isAdditiveNumberHelper (first, second, thirdStartIndex + sum.length (), num);
    }
}