java recursive for check and iterative for enumerate without long and bigInteger


  • 0
    J

    what's the time complexity for this solution? Is it O(n^3)?

     public boolean isAdditiveNumber(String num) {
        for (int i = 1; i <= num.length(); i++) {
            String num1 = num.substring(0, i);
            
            if (i != 1 && num1.startsWith("0")) return false;
            for (int j = i + 1; j <= num.length(); j++) {
                String num2 = num.substring(i, j);
                if (j != i + 1 && num2.startsWith("0")) break;
                
                if (check(num, num1, num2, j)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    public boolean check(String num, String num1, String num2, int start) {
        String res = add(num1, num2);
        int end = start + res.length();
        if (end > num.length()) return false;
        
        if (end == num.length() && res.equals(num.substring(start, end))) {
            return true;
        }
        
        if (!res.equals(num.substring(start, end))) return false;
        return check(num, num2, res, end);
    }
    
    
    public String add(String num1, String num2) {
        String res = "";
        
        int carry = 0;
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        
        while (i >= 0 && j >= 0) {
            int num = num1.charAt(i) - '0' + num2.charAt(j) - '0' + carry;
            res = num % 10 + res;
            carry = num / 10;
            i--;
            j--;
        }
        
        while (i >= 0) {
            int num = num1.charAt(i) - '0' + carry;
            res = num % 10 + res;
            carry = num / 10;
            i--;
        }
        
        while (j >= 0) {
            int num = num2.charAt(j) - '0' + carry;
            res = num % 10 + res;
            carry = num / 10;
            j--;
        }
        
        if (carry != 0) res = carry + res;
        return res;
    }

Log in to reply
 

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