Sharing my C++ solution


  • 0
    T
    class Solution {
    private:
        string add(string NUM1, string NUM2)
        {
            string num1 = NUM1;
            string num2 = NUM2;
            int n1 = num1.length();
            int n2 = num2.length();
            int N = max(n1, n2);
            int n = min(n1, n2);
            if(n1>n2)
                num2 = string(N-n, '0') + num2;
            else if(n2>n1)
                num1 = string(N-n, '0') + num1;
                
            int addOne = 0;
            int current;
            string result = "";
            for(int i=N-1; i>=0; i--)
            {
                current = addOne + (num1[i]-'0') + (num2[i]-'0');
                addOne = current/10;
                current = current%10;
                result.push_back(current+'0');
            }
            if(addOne==1)
                result.push_back('1');
                
            int left=0, right = result.length()-1;
            while(left<right)
            {
                swap(result[left], result[right]);
                left++;
                right--;
            }
            return result;
        }
    
    
        bool isAdditiveNumberHelper(string num1, string num2, string num3)
        {
            if((num1.size() > 1 && num1[0] == '0') || (num2.size() > 1 && num2[0] == '0'))
                return false;
            string total = add(num1, num2);
            int n = total.length();
            if(total==num3)
                return true;
            else if(n>=num3.length() || total!= num3.substr(0,n))
                return false;
            else
                return isAdditiveNumberHelper(num2, total, num3.substr(n));
        }
        
    public:
        bool isAdditiveNumber(string num) {
            int n = num.length();
            if(n<3)
                return false;
                
            int i, j;
            for(i=1; i<=n/2; i++)
                for(j=1; j<=(n-i)/2; j++)
                    {
                        string num1 = num.substr(0, i);
                        string num2 = num.substr(i, j);
                        string num3 = num.substr(i+j);
                        if(isAdditiveNumberHelper(num1, num2, num3))
                            return true;
                    }
                    
            return false;
        }
    };

Log in to reply
 

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