My easy to understand C++ iterative solution with string adding


  • 0
    B

    several tricks to remember

    1. string adding
    2. how to handle leading 0s
    3. recursion
    class Solution {
    public:
        string stradd(string s1, string s2) {
            int i=s1.length()-1,j=s2.length()-1,carry=0;
            string ret="";
            while(i>=0 || j>=0) {
                int sum = 0;
                if(i>=0 && j<0) sum = s1[i--]-'0'+carry;
                else if(i<0 && j>=0) sum = s2[j--]-'0'+carry;
                else sum = s1[i--]-'0'+s2[j--]-'0'+carry;
                ret = to_string(sum%10)+ret;
                carry = sum / 10;
            }
            ret = (carry>0?to_string(carry):"") + ret;
            return ret;
        }
        bool check(string str, string sum, string prev) {
            if(str[0]=='0') return sum=="0";
            string cur = "";
            int k = 0;
            while(k<str.length()) {
                cur += str[k];
                if(cur == sum && k == str.length()-1) return true;
                if(cur == sum) {k++; break;}
                if(sum.find(cur)==string::npos) return false;
                k++;
            }
            if(k<str.length() && check(str.substr(k), stradd(cur,prev), cur)) return true;
            return false;
        }
        bool isAdditiveNumber(string num) {
            if(num.length()<3) return false;
            for(int k = 0; k<num.length()-1; k++) {
                string first = num.substr(0, k+1);
                for(int l = k+1; l<num.length()-1; l++) {
                    string second = num.substr(k+1, l-k);
                    cout << second << endl;
                    if(check(num.substr(l+1), stradd(first, second), second)) return true;
                    if(num[k+1]=='0' && l==k+1) break;
                }
                if(num[0]=='0' && k==0) break;
            }
            return false;
        }
    };
    

Log in to reply
 

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