My C++ solution without using long


  • 0
    D
    class Solution {
    public:
        bool isAdditiveNumber(string num) {
    
            for(int i = 1; i < num.size() / 2 + 1; ++i) {
                string num1 = num.substr(0,i);
                if( num1.size() > 1 && num1[0] == '0' )
                    break;
                for(int j = i + 1; j < num.size(); ++j) {
                    string num2 = num.substr(i, j-i);
                    if( num2.size() > 1 && num2[0] == '0' )
                        break;
                    if( isAdditiveNumberHelper(num1, num2, num.substr(j)) )
                        return true;
                }
            }
            return false;
        }
    private:
        string stringAdd(string num1, string num2) {
            reverse(num1.begin(), num1.end());
            reverse(num2.begin(), num2.end());
            string r;
            int add = 0, i;
            for(i = 0; i < min(num1.size(), num2.size()); ++i) {
                int acc = num1[i] - '0' + num2[i] - '0' + add;
                r.push_back(acc % 10 + '0');
                add = acc / 10;
            }
            if( num1.size() < num2.size() )
                num1 = num2;
            for(; i < num1.size(); ++i) {
                int acc = num1[i] - '0' + add;
                r.push_back(acc % 10 + '0');
                add = acc / 10;
            }
            if( add )
                r.push_back(add + '0');
            reverse(r.begin(), r.end());
            return r;
        }
        bool isAdditiveNumberHelper(string num1, string num2, string num) {
             string res = stringAdd(num1, num2);
             if( res.size() > num.size() )
                return false;
             if( res == num.substr(0, res.size()) )
                    if( res.size() == num.size() )
                        return true;
                    else
                        return isAdditiveNumberHelper(num2, res, num.substr(res.size()));
            return false;
        }
    };

Log in to reply
 

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