[leetcode] 306. Additive Number 解題報告

題目鏈接:https://leetcode.com/problems/additive-number/

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should containat leastthree 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

1 + 99 = 100, 99 + 100 = 199

Note:Numbers in the additive sequencecannothave leading zeros, so sequence1, 2, 03or1, 02, 3is 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?

思路: 一個基本的思想就是確定了第一個和第二個數之後, 以後的數就是驗證了, 所以只要枚舉第一和第二個數, 然後不斷驗證下面的字符串子串是否是前兩個數的和即可. 因為數字可能超出整數的范圍, 因此在驗證一個數是否是另外兩個和的時候, 可以用字符串相加來模擬整數相加. 另外需要注意的是'0'字符, 如果他在子串的首位, 那麼他只能以"0"的形式存在, 並且"0"只可能作為第一個數或者第二個數.

代碼如下:

class Solution {
public:
    string add(string s1, string s2)
    {
        string result;
        int flag = 0, i = s1.size()-1, j = s2.size()-1;
        while(i >=0 || j >=0)
        {
            int num1=0, num2=0;
            if(i >=0) num1 = s1[i]-'0';
            if(j >= 0) num2 = s2[j]-'0';
            result.insert(result.begin(), '0'+(num1+num2+flag)%10);
            flag = (num1+num2+flag)/10;
            i--, j--;
        }
        if(flag == 1) result.insert(result.begin(), '1');
        return result;
    }
    
    bool DFS(string num, string num1, string num2)
    {
        if(num.size()==0 || num[0] == '0') return false;
        for(int i =0; i < num.size(); i++)
        {
            string x = num.substr(0, i+1); 
            if(x ==add(num1,num2))
            {
                if(i == num.size()-1) return true;
                return DFS(num.substr(i+1), num2, x);
            }
        }
        return false;
    }
    
    bool isAdditiveNumber(string num) {
        int len = num.size();
        if(len < 3) return false;
        string num1, num2;
        for(int i = 0; i < len-2; i++)
        {
            num1 = num.substr(0, i+1);
            for(int j = i+1; j < len-1; j++)
            {
                num2 = num.substr(i+1, j-i);
                if(DFS(num.substr(j+1), num1, num2)) return true;
                if(num[i+1] == '0') break;
            }
            if(num[0] == '0') break;
        }
        return false;
    }
};