My Straightforward AC Java Solution


  • 0
    S

    the solution is straightforward.
    the method isAdditiveNumber is the main function. it enumerates the start possibilities of different length of the first two numbers and skip the preceding zero cases.
    for each combination, it calls isAdditiveNumberR which is a recursive backtracking function.
    in this function, in each recursion, it checks if it meets a1+a2=a3. if it does, continue, or return false.
    three helper function here. 1) getSum do the plus operation of two int array 2) in function checks the condition of a1+a2=a3. 3) toNums convert string to int array.
    welcome any improvements.

    public class Solution {
    public boolean isAdditiveNumber(String num) {
        
        int[] nums = toNums(num);
        
        for(int i=1;i<nums.length;i++)
        {
            
            for(int j=1;j<nums.length-i;j++)
            {
                if(nums[i]==0&&j>1) break;
                if(isAdditiveNumberR(nums,0,i,i,j))
                    return true;
            }
        }
        return false;
    }
    
    public int[] toNums(String num)
    {
        int[] nums=new int[num.length()];
        for(int i=0;i<num.length();i++)
        {
            nums[i]=num.charAt(i)-'0';
        }
        return nums;
    }
    
    public boolean isAdditiveNumberR(int[] nums, int s1, int l1, int s2, int l2)
    {
        if(s2+l2==nums.length)
        {
            return true;
        }
        
        int[] sum = getSum(nums,s1,l1,s2,l2);
        if(in(nums,sum,s2+l2))
        {
            return isAdditiveNumberR(nums,s2,l2,s2+l2,sum.length);
        }
        else
        {
            return false;
        }
    }
    
    public boolean in(int[] nums,int[] sum, int start)
    {
        if(start+sum.length>nums.length) return false;
        for(int i=0;i<sum.length;i++)
        {
            if(nums[start+i]!=sum[i]) return false;
        }
        return true;
    }
    
    public int[] getSum(int[] nums, int s1, int l1, int s2, int l2)
    {
        int[] sum = new int[Math.max(l1,l2)+1];
        int len = sum.length;
        int carrier = 0;
        while(l1>0||l2>0)
        {
            int v1 = l1>0?nums[s1+l1-1]:0;
            int v2 = l2>0?nums[s2+l2-1]:0;
            int s = v1+v2 + carrier;
            sum[len-1]=s%10;
            carrier=s/10;
            len--;
            l1--;
            l2--;
        }
        sum[0]=carrier;
        if(sum[0]==0)
        {
            return Arrays.copyOfRange(sum,1,sum.length);
        }
        return sum;
    }
    

    }


Log in to reply
 

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