C++ 0ms, string addition


  • 2

    Once the first two numbers are determined, the rest sequence is determined. So we can check all the possible choices of first two numbers to see whether the rest sequence is valid or not.

    string add(string s1, string s2){
    string res;
    int sz1=s1.size(),sz2=s2.size();
    int sz = sz1>sz2?sz1:sz2;
    s1 = string(sz-sz1,'0')+s1;
    s2 = string(sz-sz2,'0')+s2;
    res = s2;
    int flag = 0,temp;
    for (int i=sz-1;i>=0;i--){
        temp = s1[i]-'0'+s2[i]-'0'+flag;
        flag = (temp>9);
        res[i]=temp-10*flag+'0';
    }
    if (flag) res='1'+res;
    return res;
    }
    
    class Solution {
    public:
    bool isAdditiveNumber(string num) {
        int sz=num.size();
        if (sz<3) return false;
        string num1,num2,num3;
        int rL;
        for(int i=1;i<=sz-2 && i<=10;i++){
            if (num[0]=='0' && i>1) break;
            for(int j=1;j<=sz-i-1 && j<=10;j++){
                rL = sz-i-j;
                num1=num.substr(0,i);
                num2=num.substr(i,j);
                num3=add(num1,num2);
                if (num[i]=='0' && j>1) break;
                while (1){
                    if (num3.size()>rL) break;
                    if (num.substr(sz-rL,num3.size())!=num3) break;
                    rL-= num3.size();
                    if (rL==0) return true;
                    num1=num2;
                    num2=num3;
                    num3=add(num1,num2);
                }
            }
        }
        return false;
    }
    };

  • 0
    Q

    Great solution.


Log in to reply
 

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