2ms very short java solution, avoid parsing every number


  • 0
    M
    import java.math.BigInteger;
    
    public class Solution {
        public boolean isAdditiveNumber(String num) {
            int n = num.length();
              for (int i = 1; i <= n / 2; ++i) {              
                  for (int j = 1;  Math.max(i, j) <= (n - i -j); ++j) {
                     if ((num.charAt(0) == '0' && i > 1) || (num.charAt(i) == '0' && j > 1) || (num.charAt(i+j) == '0' && (i + j > 2))) continue;              
                     Long first =  Long.parseLong(num.substring(0, i)); 
                     Long second =  Long.parseLong(num.substring(i, i+j));                 
                     int start = i + j;                  
                     while(start < num.length()) { 
                         Long third = first + second;
                         String thirdStr = "" + third; 
                         if (!num.startsWith(thirdStr, start)) break;
    
                         first = second;
                         second = third;
                         start += thirdStr.length();
                     }
                     if (start == num.length()) return true;
                  }
            } 
            return false;
        }
    }
    

Log in to reply
 

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