C++ Solution 0 ms


  • 0
    J
    class Solution {
    private:
        string add(string num1, string num2){
            int len = max(num1.length(), num2.length());
            string result("");
            char carry = 0;
            for(int i = num1.length()-1, j = num2.length()-1; 
                    i >= 0 || j >= 0; 
                    i--, j--){
                char n1 = i >= 0 ? num1.at(i) : '0';
                char n2 = j >= 0 ? num2.at(j) : '0';
                n1 -= '0';
                n2 -= '0';
                char n = (n1 + n2 + carry)%10;
                n += '0';
                carry = (n1 + n2 + carry) > 9 ? 1 : 0;
                result = n + result;
            }
            if(carry != 0){
                carry += '0';
                result = carry + result;
            }
            return result;
        }
        bool valid(string num1, string num2, string remain){
            string sum = add(num1, num2);
            if(remain.length() < sum.length()){
                return false;
            }
            if(remain.compare(sum) == 0){
                return true;
            }
            if(remain.substr(0, sum.length()).compare(sum) != 0){
                return false;
            }
            return valid(num2, sum, remain.substr(sum.length()));
        }
    public:
        bool isAdditiveNumber(string num) {
            if(num.length() < 3){
                return false;
            }
            for(int len1 = 1; len1 <= num.length()/2; len1++){
                for(int len2 = 1; len2 <= num.length()/2; len2++){
                    string num1 = num.substr(0, len1);
                    string num2 = num.substr(len1, len2);
                    string remain = num.substr(len1+len2);
                    if(valid(num1, num2, remain)){
                        return true;
                    }
                }
            }
            return false;
        }
    };

  • 0
    E

    It does not work for "10203". The program returns true. By definition, the answer should be false.


Log in to reply
 

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