My Recursive Solution In Java


  • 0
    B
     public boolean isAdditiveNumber(String num) {
    		if (num.length()<3) {
    			return false;
    		}
    		 int preLen = num.length()/2;
    		if (num.charAt(0)=='0') {
    			preLen = 1;
    		}
    		for(int i=1;i<=preLen;i++){
    			String sLast = num.substring(0,i);
    			if (isAdditiveNumberWithLastNumber(num.substring(i), sLast)) {
    				return true;
    			}
    		}
    		return false;
    	}
    	public boolean isAdditiveNumberWithLastNumber(String num,String last){
    		if (num.length()<last.length()) {
    			return false;
    		}
    		final long nLast = Long.valueOf(last);
    		int nextLimit = num.length() - last.length();
    		if (num.charAt(0)=='0') {
    			nextLimit = 1;
    		}
    		for(int i=1;i<=nextLimit;i++){
    			String sNext = num.substring(0,i);
    			long nNext = Long.valueOf(sNext);
    			
    			long nSum = nLast+nNext;
    			String sSum = String.valueOf(nSum);
    			
    			if (sSum.length()+i>num.length()) {
    				return false;
    			}
    			long sumFromNum = Long.valueOf(num.substring(i,i+sSum.length()));
    			if (nSum==sumFromNum) {
    				String nextNum = num.substring(i);
    				if (nextNum.length()==sSum.length() || isAdditiveNumberWithLastNumber(num.substring(i),sNext)) {
    					return true;
    				}
    			}
    		}
    		return false;
    	}

Log in to reply
 

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