[JAVA] My easy-understanding solution with explanation


  • 1
    C

    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 isAdditiveNumberHelper(num, i+1, pre2, curNum);
            }
            
            return false;
        }
        
        public boolean isAdditiveNumber(String num) {
            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));
                    if(isAdditiveNumberHelper(num, j+1, num1, num2))
                        return true;
                }
            }
            
            return false;
        }

  • 2

    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 {
    
      public boolean isAdditiveNumber(String num) {
        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);
      }
      
    }
    

  • 0
    C

    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!


  • 0

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


Log in to reply
 

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