Short CPP solution with explanation.


  • 0
    H

    We can decide whether the number is additive number right after we have chosen the first two numbers.
    The following recursive calls are just verifications.

    class Solution {
    public:
        bool isAdditiveNumber(string num) {
            if (num.size() < 3) return false;
            // get all possible combination of the first two numbers.
            for (int i = 1; i <= num.size() - 2; ++i) {
                for (int j = i+1; j <= num.size() - 1; ++j) {
                    if (isAdditiveNumber(num.substr(0, i), num.substr(i, j-i), num.substr(j))) return true;
                }
            }
            return false;
        }
        
        bool isAdditiveNumber(string preStr,  string curStr, string &&num) {
            if ((preStr.size() > 1 && preStr[0] == '0') || (curStr.size() > 1 && curStr[0] == '0')) return false;
    
            long pre = stol(preStr), cur = stol(curStr);
            string nextStr = to_string(pre + cur);
            
            if (nextStr.size() > num.size() || num.substr(0, nextStr.size()).compare(nextStr)) return false;
            if (nextStr.size() == num.size()) return true;
            
            preStr = curStr;
            curStr = nextStr;
            return isAdditiveNumber(preStr, curStr, num.substr(nextStr.size()));
        }
    };

Log in to reply
 

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