Java 3ms Solution without recursive


  • 0
    M
    public class Solution {
        public boolean isAdditiveNumber(String num) {
            if (num=="")
            	return false;
            for (int i=1;i<num.length()-1;i++) {
            	if (i>=num.length()-i)
            		return false;
            	if (num.charAt(0)=='0' && i>1)
            		return false;
            	for (int j=i+1;j<num.length();j++) {
            		if (num.charAt(i)=='0' && j>i+1)
            			break;
            		if (j-i>num.length()-j)
            			break;
            		if (num.charAt(j)=='0')
            			continue;
            		Long left=Long.parseLong(num.substring(0, i));
            		Long right=Long.parseLong(num.substring(i, j));
            		String sum=Long.toString(left+right);
            		String other=num.substring(j, num.length());;
            		while (other.length()>0 && !other.startsWith("0")) {
    	        		if (!other.startsWith(sum))
    	        			break;
    	        		other=other.substring(sum.length());
    	        		left=right;
    	        		right=Long.valueOf(sum);
    	        		sum=Long.toString(left+right);
            		}
            		if (other.length()==0)
            			return true;
            	}
            }
            return false;
        }
    }

Log in to reply
 

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