JAVA 1 ms solution, a little long ;D


  • 0

    Hmm.., it's hard to say that this question belongs to which type of questions. Backtracking maybe. The basic idea is "brute force". A little tricky part is to avoid obviously futile searching case.

    public boolean isAdditiveNumber(String num) {
        int p1=1;
        int p2=1;
        int len=num.length();
        while(p1<=len/2)
        {
            p2=1;
            while(p1+p2<=len*2/3)
            {
                int i1=convertStringtoInt(num.substring(0,p1));
                int i2=convertStringtoInt(num.substring(p1,p1+p2));
                int start=p1+p2;
                int l=Math.max(p1,p2);
                if(start+l>len) break;
                int test=convertStringtoInt(num.substring(start,start+l));
                if(test==-1) 
                {
                    p2++;
                    continue;
                }
                while(start+l<=len)
                {
                    int i3=i1+i2;
                    if(test<i3) 
                    {
                        if(test==0) break;
                        test*=10;
                        if(start+l==len) break;
                        test+=num.charAt(start+l)-'0';
                        l++;
                    }
                    else if(test>i3) break;
                    else
                    {
                        if(start+l==len) return true;
                        start=start+l;
                        l=Math.max(p1,p2);
                        if(start+l>len) break;
                        test=convertStringtoInt(num.substring(start,start+l));
                        if(test==-1) break;
                        i1=i2;
                        i2=i3;
                    }
                }
                p2++;
            }
            p1++;
        }
        return false;
    }
    public int convertStringtoInt(String a)
    {
        if(a.charAt(0)=='0'&&a.length()>1) return -1;
        int sum=0;
        for(int i=0;i<a.length();i++)
        {
            sum*=10;
            sum+=a.charAt(i)-'0';
        }
        return sum;
    }

Log in to reply
 

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