# [JAVA] My easy-understanding solution with explanation

• The thought is direct forward:

1. Call the helper function for each possible combination of first two numbers.

2. While in the helper function, we check whether there exists a number whose value equals to the sum of the two previous numbers. If there exists such a number, we do the recursive call to check the reminding part of the string; if such a number doesn't, the number represented by the string cannot be an additive number, we could just return false.

3. Deal with leading 0 cases.

But I'm not very clear with the time complexity. Would anyone help me?

``````public boolean isAdditiveNumberHelper(String num, int cur, long pre1, long pre2) {
if(cur==num.length())
return true;

for(int i=cur; i<num.length(); i++) {
if(num.charAt(cur)=='0' && i>cur)
continue;

long curNum = Long.parseLong(num.substring(cur, i+1));

if(curNum==pre1 + pre2)
}

return false;
}

if(num==null || num.length()<3)   return false;

for(int i=0; i<num.length()-2; i++) {
long num1 = Long.parseLong(num.substring(0, i+1));
for(int j=i+1; j<num.length()-1; j++) {
if(num.charAt(i+1)=='0' && j>i+1)
continue;

Long num2 = Long.parseLong(num.substring(i+1, j+1));
return true;
}
}

return false;
}``````

• Hi @chengyu7, your solution is good, but we can optimize a little bit by replacing all the `continue` with `break`. Basically once we find a number in the additive sequence has leading zeros, we don't need to look ahead.

In terms of the time complexity, here is what I thought:

in the worst case, first it takes us `O(n^2)` time to try all the first two numbers `num1` (for loop `i`) and `num2` (for loop `j`), then inside the inner loop, we call `isAdditiveNumberHelper` to check if the rest numbers match the definition of additive number.

From my point of view, what the helper function does is just try to iterate through the two numbers in `num`, so overall the time complexity should be `O(n^3)`.

Actually there's a better way to do the helper, suppose `pre1` is `12`, `pre2` is `100`, then we know that `curNum` should be `112`, its length is `3`, so we can try `curNum` in `O(1)` time.

If you look at other posts, we can also use iterative way to implement the helper, it will help you understand the time complexity, but I like your recursive solution!

I modified your solution as follows:

``````public class Solution {

if (num == null || num.length() < 3) {
return false;
}

for (int i = 0; i < num.length() - 2; i++) {
if (num.charAt(0) == '0' && i > 0) {
break;
}

long num1 = Long.parseLong(num.substring(0, i + 1));

for (int j = i + 1; j < num.length() - 1; j++) {
if (num.charAt(i + 1) == '0' && j > i + 1) {
break;
}

Long num2 = Long.parseLong(num.substring(i + 1, j + 1));

if (helper(num, j + 1, num1, num2)) {
return true;
}
}
}

return false;
}

public boolean helper(String num, int index, long num1, long num2) {
if (index == num.length()) {
return true;
}

long cur = num1 + num2;
String str = String.valueOf(cur);

// if exceeded or the sum doesn't match
// use string comparison to avoid things like "12 + 12 = 024"
if (!num.startsWith(str, index)) {
return false;
}

return helper(num, index + str.length(), num2, cur);
}

}
``````

• Great Improvements! The check of existence of curNum, whose value should equal to the sum of pre1 and pre2, could only take O(1) time complexity. And now each run of helper function only takes O(1) time, the overall time complexity is much clearer. Appreciated for the help!

• No worries mate :) I modified the above code to use `startsWith()`, that makes the code cleaner.

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