java 3ms clean and easy understood recursive code


  • 0
    D
    public boolean isAdditiveNumber(String num) {
        int len = num.length();
        if(len<3)
            return false;
        for(int i = 0;i<len/2;i++){   // String A from 0 to i , inclusive  , has i+1 char
            for(int j = i+1; len-1-j>=i+1&&len-1-j>=j-i;j++){   // String B from i+1 to j ,inclusive has j-i char
            // the remain part from j+1 to len -1, has len-1-j char 
                if(isValid(0,i,j,num))
                    return true;
            }
        }
        return false;
    }
    
    
    public boolean isMatch(String a,String b , String c){
        if(a.charAt(0)=='0'&&a.length()!=1)
            return false;
        if(b.charAt(0)=='0'&&b.length()!=1)
            return false;
        if(c.charAt(0)=='0'&&c.length()!=1)
            return false;
        int len_a = a.length();
        int len_b = b.length();
        String sum = "";
        int carry = 0;
        for(int i = 0;i<len_a||i<len_b;i++){
            if(i<len_a)
                carry += (a.charAt(len_a-1-i) -'0');
            if(i<len_b)
                carry += (b.charAt(len_b-1-i) -'0');
            sum = carry%10 + sum;
            carry /= 10;
        }
        if(carry ==1)
            sum = 1+ sum ;
        return c.equals(sum);
    }
    
    public boolean isValid(int begin, int i, int j, String num){
        boolean res = false;
        if(j==num.length()-1){
            return true;
        }
        for(int k = j+1;k<num.length();k++){   // from j+1 to k , has k-j char
            if(k-j>=j-i){         //from i +1 to j , has j-i  char,  from begin to i , has i-begin+1 char
                String a = num.substring(begin,i+1);
                String b = num.substring(i+1,j+1);
                String c = num.substring(j+1,k+1);
                if(isMatch(a,b,c)){
                    res = res | isValid(i+1,j,k,num);
                }
            }
        }
        return res;
    }

Log in to reply
 

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