Java recursive solution + explanation


  • 0
    A

    Recursive solution. Divided given num into three parts. Then check wether we can get sum of first two parts from third part. If not, we check wether third part starts with sum of first and second. If so, we run recursion. Recursion paramters will be (secondPart, firstPart+secondPart , left part).

    import java.math.BigInteger;
    
    public class Solution {
        public boolean isAdditiveNumber(String num) {
            for (int i=1; i<num.length(); i++) {
                for (int j=i+1; j<num.length(); j++) {
                    String f = num.substring(0,i);
                    String s = num.substring(i,j);
                    String last = num.substring(j);
                    if (check(f,s,last)) return true;
                }
            }
            return false;
        }
        
        private boolean check(String f, String s, String last) {
            if (isLeadingZero(f)) return false;
            if (isLeadingZero(s)) return false;
            
            String sum = ((new BigInteger(f)).add(new BigInteger(s))).toString();
            if (sum.equals(last)) return true;
            
            if (last.length()<sum.length()) return false;
            if (!last.substring(0, sum.length()).equals(sum)) return false;
            
            return check(s, sum, last.substring(sum.length()));
        }
        
        private boolean isLeadingZero(String num) {
            return (num.length()>1 && num.charAt(0)=='0');
        }
    }
    

Log in to reply
 

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