0ms concise C++ solution (perfectly handles the follow-up and leading 0s)


  • 65
    Z

    use a helper function to add two strings.

    Choose first two number then recursively check.

    Note that the length of first two numbers can't be longer than half of the initial string, so the two loops in the first function will end when i>num.size()/2 and j>(num.size()-i)/2, this will actually save a lot of time.

    Update the case of heading 0s
    e.g. "100010" should return false

    class Solution {
    public:
            bool isAdditiveNumber(string num) {
                for(int i=1; i<=num.size()/2; i++){
                    for(int j=1; j<=(num.size()-i)/2; j++){
                        if(check(num.substr(0,i), num.substr(i,j), num.substr(i+j))) return true;
                    }
                }
                return false;
            }
            bool check(string num1, string num2, string num){
                if(num1.size()>1 && num1[0]=='0' || num2.size()>1 && num2[0]=='0') return false;
                string sum=add(num1, num2);
                if(num==sum) return true;
                if(num.size()<=sum.size() || sum.compare(num.substr(0,sum.size()))!=0) return false;
                else return check(num2, sum, num.substr(sum.size()));
            } 
            string add(string n, string m){
                string res;
                int i=n.size()-1, j=m.size()-1, carry=0;
                while(i>=0 || j>=0){
                    int sum=carry+(i>=0 ? (n[i--]-'0') : 0) + (j>=0?  (m[j--]-'0') : 0);
                    res.push_back(sum%10+'0');
                    carry=sum/10;
                }
                if(carry) res.push_back(carry+'0');
                reverse(res.begin(), res.end());
                return res;
            }
        };

  • 0
    Z

    Implement string addition is a boost!


  • -10
    J
    bool isAdditiveNumber(string num) {
        //return isAdditiveHelper(num,10,1,2147483647,0);
        if(num.length()<3)
            return false;
        int step=0;
        //防止越界
        long front=0,second=0;
        for(int i=0;i<num.length()-1;){
            front=front*10+num[i]-'0';
            int j=i+1;
            second=0;
            for(;j<num.length();){
                if(j==i+1&&num[j]=='0'){
                    second=0;
                    if(isAdditiveHelper(num,j,front,second,0))
                        return true;
                    else
                        break;
                }else{
                    second=second*10+num[j]-'0';
                    if(isAdditiveHelper(num,j,front,second,0))
                        return true;
                    ++j;
                }
            }
            ++i;
        }
        return false;
    }
    
    bool isAdditiveHelper(string num,int step,long front,long second,int depth){
        if(depth==0&&step==num.length()-1)
            return false;
        else if(depth>0&&step==num.length()-1){
            return true;
        }
        string temp=num.substr(step+1,num.length()-step-1);
        long result_should=front+second;
        long res_get=0;
        int i=0;
        for(;i<temp.length();){
            if(i==0&&temp[i]=='0'){
                return false;
            }
            res_get=res_get*10+temp[i]-'0';
            if(res_get>result_should)
                return false;
            else if(res_get==result_should){
                return isAdditiveHelper(num,i+step+1,second,result_should,depth+1);
            }
            ++i;
        }
        return false;
    }
    

  • 1

    In the last line of check, you can simply write

    return check(num2, sum, num.substr(sum.size()));
    

  • 0
    Z

    You are right. Thanks for advise!


  • 0
    D

    The test data is too weak.when I input the "100010",I get the answer "1".Obviously,the output should be "0"


  • 0

    Why the output of 100010 is 0 (false)? It is 1 (true): 10 + 0 + 0 = 10.


  • 0
    D

    Each subsequent number in the sequence must be the sum of the preceding two,while "10 + 0 + 0" contains three numbers. According to the code above, the answer is "10 + 00 = 10"


  • 0

    Oh, I mistaken the problem. But I try the above code on 100010 and the output is actually false. Have you made sure you rewrite the code perfectly correctly?


  • 0
    T

    Great idea, but how did you handle the leading zero constraint?


  • 0
    Z

    You are right. I have not handled the '00' case. Thanks for pointing out.


  • 0
    T

    A small change on your code to handle the leading zero case:

    for(int len1 = 1; len1 <= num.size() / 2; ++len1)
    {
        string s1 = num.substr(0, len1);
        if(s1[0] == '0' && len1 > 1) break;
        for(int len2 = 1; len2 <= (num.size() - len1) / 2; ++len2)
        {
            string s2 = num.substr(len1, len2);
            if(s2[0] == '0' && len2 > 1) break;
            if(helper(s1, s2, num.substr(len1 + len2)))
                return true;
        }
    }

  • 0
    Z

    Thanks. I already updated the code.~


  • 0
    J

    You code would fail for the test case: 101.

    if(num1.size()>0 && num1[0]=='0' || num2.size()>0 && num2[0]=='0') return false;
    

    should be

    if(num1.size()>1 && num1[0]=='0' || num2.size()>1 && num2[0]=='0') return false;

  • 0
    Z

    Just a typo. Thanks for pointing out~


  • 0
    J

    Great solution! I learn a lot from your solution. And nice implementation of string add.


  • 0
    Z

    : ) Glad you say that, bro


  • 0
    T

    I think this line needs update:
    if(num.size()<=sum.size() || sum.compare(num.substr(0,sum.size()))!=0) return false;

    should be:
    if(num.size()<sum.size()


  • 5
    X

    Java solution based on your code.

    private String add(String a, String b) {
        StringBuilder rst = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry + (i >= 0 ? a.charAt(i--) - '0' : 0) + (j >= 0 ? b.charAt(j--) - '0' : 0);
            rst.insert(0, sum % 10);
            carry = sum / 10;
        }
        return rst.toString();
    }
    
    private boolean check(String a, String b, String c) { 
    	if (a.length() > 1 && a.charAt(0) == '0' || b.length() > 1 && b.charAt(0) == '0') return false;
    	String sum = add(a, b);
    	if (sum.equals(c)) return true;
    	if (c.length() <= sum.length() || !c.substring(0, sum.length()).equals(sum)) return false;
    	return check(b, sum, c.substring(sum.length()));
    }
    
    public boolean isAdditiveNumber(String num) {
        for (int i = 1; i <= (num.length() >> 1); i++) {
        	for (int j = 1; j <= ((num.length() - i) >> 1); j++) {
        		if (check(num.substring(0, i), num.substring(i, i + j), num.substring(i + j))) return true;
        	}
        }
        return false;
    }

  • -1
    H
    string add(string n, string m) {
        string res = to_string(atoll(n.c_str()) + atoll(m.c_str()));
        return res;
    }

Log in to reply
 

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