Share my cpp 0ms recursive solution


  • 0
    W

    Should be a DFS solution with O(n^2) time

    note that my code cannot solve the follow up problem.

    class Solution {
    public:
        bool isAdditiveNumber(string num) {
            for(int i = 1; i < num.size() / 2 + 1; i++)
                if(isAdditiveNumber(num, 0, i))
                    return true;
            return false;
        }
    
    private:
        bool isAdditiveNumber(string num, int idx, int i /* length of the first num */) {
            for(int j = 1; idx + i + j <= num.size() - j; j++) /* length of the second num */ {
                if(j > 1 && num[idx + i] == '0') // start with zero
                    return false;
                long num1 = atol(num.substr(idx, i).c_str());
                long num2 = atol(num.substr(idx + i, j).c_str());
                if(num.find(to_string(num1 + num2), idx + i + j) == idx + i + j) {
                    if(to_string(num1 + num2).length() + idx + i + j == num.length() ||
                        isAdditiveNumber(num, idx + i, j))
                        return true;
                }
            }
            return false;
        }
    };

  • 0
    L

    Your code didn't pass the case: "0235813".
    It is false from the expected answer but your code gives true.


  • 0
    L

    You can add one if statement before if(isAdditiveNumber(num, 0, i)). The if statement is:

    if(i>1 && num.charAt(0) == '0') return false;
    

Log in to reply
 

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