C++ 0ms Solution


  • 0
    class Solution{
    	bool isAdd(string num, int pos, long first, long second, int count)
    	{
    		if (first == -1)
    		{
    			if (pos >= num.size() - 2) return false;
    			if (num[pos] == '0') return isAdd(num, pos + 1, 0, -1, 1);
    			long val = 0;
    			for (int idx = pos; idx < num.size(); ++idx)
    			{
    				val = val * 10 + (num[idx] - '0');
    				if (isAdd(num, idx + 1, val, -1, 1)) return true;
    			}
    			return false;
    		}
    		else if (second == -1)
    		{
    			if (pos >= num.size() - 1) return false;
    			if (num[pos] == '0') return isAdd(num, pos + 1, first, 0, 2);
    			long val = 0;
    			for (int idx = pos; idx < num.size(); ++idx)
    			{
    				val = val * 10 + (num[idx] - '0');
    				if (isAdd(num, idx + 1, first, val, 2)) return true;
    			}
    			return false;
    		}
    		else
    		{
    			string sum = to_string(first + second);
    			if (pos == num.size() && count > 2)
    				return true;
    			else if (pos < num.size() && sum == num.substr(pos, sum.size()))
    				return isAdd(num, pos + sum.size(), second, first + second, count + 1);
    			else
    				return false;
    		}
    	}
    public:
    	bool isAdditiveNumber(string num)
    	{
    		if (num.size() < 3) return false;
    		return isAdd(num, 0, -1, -1, 0);
    	}
    };
    

Log in to reply
 

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