My c++ solution use recursion


  • 0
    H
       class Solution {
    public:
        bool isAdditiveNumber(string num) {
            int len = num.size();
            int maxlen = len/2;
            int i = 1, j = 1;
            for(i=1; i<=maxlen; ++i){
                for(j=1; j<=maxlen; ++j){
                    if(len-i-j<i || len-i-j<j)
                        continue;
                    if(couldFormSequence(i,j,num))
                        return true;
                }
            }
            return false;
        }
        
        string stringPlus(string& a, string& b){
            int len_a = a.size();
            int len_b = b.size();
            int k = 0;
            string r;
            int c = 0;
            for(int i=a.size()-1,j=b.size()-1; i>=0||j>=0; --i,--j,++k){
                int num1 = 0;
                int num2 = 0;
                if(i>=0)
                    num1 = a[i]-'0';
                if(j>=0)
                    num2 = b[j]-'0';
                int num = num1+num2+c;
                r.push_back(num%10 + '0');
                c = num/10;
            }
            if(c == 1)
                r.push_back(1+'0');
            reverse(r.begin(), r.end());
            return r;
        }
        
        bool couldFormSequence(int i, int j, string num){
            string n1 = num.substr(0,i);
            string n2 = num.substr(i,j);
            if((n1.size()>1&&n1[0]=='0') || (n2.size()>1 && n2[0] == '0'))
                return false;
            string sum = stringPlus(n1,n2);
            if(sum == num.substr(i+j,sum.size()) && sum.size()+i+j==num.size())
                return true;
            else if(sum == num.substr(i+j,sum.size()))
                return couldFormSequence(j, sum.size(), num.substr(i));
            return false;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.