C++ recursive solution


  • 0
    G
    class Solution {
    public:
        
        bool isAdditiveHelper(const string &n, const string &first, const string &second){
            if(n.empty()){
                return true;
            }
            
            istringstream ss1(first), ss2(second);
            long long f,s;
            ss1 >> f;
            ss2 >> s;
            long long res = f + s;
            ostringstream r;
            r << res;
            
            if(n.find(r.str()) == 0){
                return isAdditiveHelper(n.substr(r.str().size()),second,r.str());
            }
            
            return false;
        }
        
        bool isAdditive(const string &num){
            
            for(int i = 1; i <= num.size() - 2; ++i){
                for(int j = 1; i + j <= num.size() - 1; ++j){
                    string first = num.substr(0,i);
                    string second = num.substr(i,j);
                    
                    if(first.size() > 1 && first[0] == '0'){
                        return false;
                    }
                    
                    if(second.size() > 1 && second[0] == '0'){
                        break;
                    }
                    
                    if(isAdditiveHelper(num.substr(i + j),first,second)){
                        return true;
                    }
                }
            }
            
            return false;
        }
        
        bool isAdditiveNumber(string num) {
            if(num.size() < 3){
                   return false;
            }
            
            return isAdditive(num);
        }
    };
    

Log in to reply
 

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