C++ straightforward solution


  • 1
    J
    bool isAdditiveNumber(string num, string last1, string last2) {
    	if (num[0] == '0' && num.length() > 1 || last1[0] == '0' && last1.length() > 1 || last2[0] == '0' && last2.length() > 1)
    		return false;
    
    	long long sum = stoll(last1) + stoll(last2);
    	int length = (int)log10(sum) + 1;
    	if (sum != stoll(num.substr(0, (int)log10(sum) + 1)))
    		return false;
    	if (num.substr(length).length() == 0)
    		return true;
    
    	return isAdditiveNumber(num.substr(length), last2, num.substr(0, length));
    }
    
    bool isAdditiveNumber(string num) {
    	for (int i = 1; i<num.length(); i++) {
    		for (int j = 1; j<num.length(); j++) {
    			if (i + j >= num.length()) continue;
    			if (isAdditiveNumber(num.substr(i + j), num.substr(0, i), num.substr(i, j)))
    				return true;
    		}
    	}
    
    	return false;
    }

Log in to reply
 

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