Java 0ms non-recursive solution with explanation


  • 0
    L

    Normal solutions traverse the string from left to right, but mine does this reversely. It brings two obvious benefits: 1. easy to determine the range of sum (1 to len/2) and the range of one addend (1 to sum.length); 2. easy to locate the suffix of the other addend, so that we can directly compare the three corresponding digits.

    The string is partitioned like this:

    0..............a (j)...........b (i).....c (len)

    |_............._|_addend_|_sum_|

    Below is my code:

       public boolean isAdditiveNumber(String num) {
            if(num == null)
                return false;
            int len = num.length(), len1 = len - 1;
            if(len < 3)
                return false;
            char[] carray = num.toCharArray();
            int bound = (len + 1) / 2, bound2, a, b, c = len, idx;
            for(int i = len1;i >= bound;i--){
                if(i < len1 && carray[i] == '0') //leading zero
                    continue;
                b = i;
                bound2 = 2 * i - len; //len - i >= i - j
                for(int j = i-1;j >= bound2;j--){
                    if(j < i - 1 && carray[j] == '0') //leading zero
                        continue;
                    a = j;
                    while((idx = getSuffix(carray, a, b, c)) >= 0){
                        if(idx == 0)
                            return true;
                        c = b;
                        b = a;
                        a = idx;
                    }
                    b = i;
                    c = len;
                }
            }
            return false;
        }
        
        private int getSuffix(char[] num, int a, int b, int c){
    //    	System.out.println(String.valueOf(num, 0, a) + " " + String.valueOf(num, a, b-a) + " " + String.valueOf(num, b, c-b));
            boolean borrow = false, leadingZero = false;
            int i = a - 1, j = b - 1, k = c - 1, x, y, z, zeros = 0; 
            while(k >= b){
                z = num[k--] - '0';
                if(borrow)
                    z--;
                y = j >= a ? num[j--] - '0' : 0;
                if(z < y){
                    borrow = true;
                    z += 10;
                }
                else
                    borrow = false;
                if(y != z){
                    if(leadingZero && zeros > 0){
                        while(i >= 0 && zeros > 0){
                            if(num[i--] != '0')
                                return -1;
                            zeros--;
                        }
                        if(zeros > 0)
                            return -1;
                    }
                    if(i < 0)
                    	return -1;
                    x = num[i--] - '0';
                    if(x + y != z)
                        return -1;
                    leadingZero = false;
                    zeros = 0;
                }
                else if(leadingZero)
                    zeros++;
                else{
                    if(i == a - 1){
                        if(num[i--] != '0')
                            return -1;
                        leadingZero = true;
                    }
                    else{
                        leadingZero = true;
                        zeros++;
                    }
                }
            }
            
            return i + 1;
        }

Log in to reply
 

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