C++ 0ms solution (using string addition)


  • 0
    A
    class Solution {
    public:
        bool isAdditiveNumber(string num) {
            int n = num.size();
            if (n < 3) return false;
            int start = 0, end = n / 3 - 1; // e.g. if n == 11, end = 2; if n == 10, end = 2
            for (int i = start; i <= end; ++i){
                string s1 = num.substr(start, i - start +1);
                if (s1[0] == '0' && i > start) continue;
                for (int j = i + 1; j < n - (n - i - 1) / 2; ++j){
                    string s2 =  num.substr(i+1, j - i);
                    if (s2[0] == '0' && j > i + 1) continue;
                    if (isMatch(num, s1, s2, j + 1)) return true;
                }
            }
            for (int i = end + 1; i <= (n-1) / 2; ++i){
                string s1 = num.substr(start, i - start +1);
                if (s1[0] == '0' && i > start) continue;
                for (int j = i + 1; j < n - (i - start + 1); ++j){
                    string s2 =  num.substr(i+1, j - i);  
                    if (s2[0] == '0' && j > i + 1) continue;
                    if (isMatch(num, s1, s2, j + 1)) return true;
                }
            }        
            
            return false;
        }
        // after fixing the first two inputs 
        bool isMatch(string& num, string& lhs, string& rhs, int pos){
            string prefix = addString(lhs, rhs);
            if (pos == num.size()) return true;
            int n = prefix.size();
            if (n > num.size() - pos) return false;
            if (prefix != num.substr(pos, n)) return false;
            return isMatch(num, rhs, prefix, pos + n);
        }
        // string addition
        string addString(string s1, string s2){
            int n1 = s1.size(), n2 = s2.size();
            if (n1 == 0 || n2 == 0) return n1 == 0 ? s2 : s1;
            reverse(s1); reverse(s2);
            string s = "";
            int pos = 0, carry = 0;
            while (pos < min(n1, n2)){
                int sum = carry + (s1[pos] - '0') + (s2[pos] - '0');
                carry = sum / 10;
                s += (sum % 10 + '0');
                ++pos;
            }
            if (n1 == n2 && carry == 1) s += '1';
            else if (n1 > n2){
                while (pos < n1){
                    int sum = carry + s1[pos] - '0';
                    carry = sum / 10;
                    s += (sum % 10 + '0');
                    ++pos;
                }
                if (carry == 1) s += '1';
            }
            else {
                // n1 < n2
                while (pos < n2){
                    int sum = carry + s2[pos] - '0';
                    carry = sum / 10;
                    s += (sum % 10 + '0');
                    ++pos;
                }
                if (carry == 1) s += '1';            
            }
            reverse(s);
            return s;
        }
        // reverse function 
        void reverse(string& s){
            int n = s.size();
            int i = 0, j = n - 1;
            while (i < j){
                s[i] ^= s[j] ^= s[i] ^= s[j];
                ++i; --j;
            }
        }
    };

Log in to reply
 

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