Java recursive - simple dfs solution


  • 0
    R

    In this solution, I have run a dfs on the string using the string addition and equals method. The methods are self explanatory. I was planning to use Map<> for memoization, but there seems to no advantage of it in this problem.

    public class Solution {
        public boolean isAdditiveNumber(String num) {
            if(num.length() <=2)
                return false;
            
            Map<String,Boolean> map = new HashMap<String,Boolean>();
            
            return isAdditiveAux(num,"0","0",1,map);
        }
        public boolean isAdditiveAux(String num, String prev, String prevprev, int level,Map<String,Boolean> map) {
            if(num == null || num.length() == 0 ) {
                return level <= 3 ? false : true;
            }
           
            for(int i=1; i<=num.length(); i++) {
                String x = num.substring(0,i);
                if(!parsable(x))
                    return false;
                if(level >= 3) { 
                    if(!x.equals(add(prev,prevprev)))
                        continue;
                }
                if(isAdditiveAux(num.substring(i),x,prev,level+1,map)){
                    return true;
                }
            }
            return false;
        }
        public boolean parsable(String x) {
            if(x.length() > 1 && x.charAt(0) == '0')
                return false;
            return true;
        }
        public String add(String x, String y) {
            if(x == null || y == null || x.length() == 0 || y.length() == 0) {
                return (x == null || x.length() == 0) ? y : x;
            }
            
            StringBuilder output = new StringBuilder();
            
            int carry = 0;
            int i = x.length()-1;
            int j = y.length() -1;
            
            while( i >= 0 || j >=0 || carry > 0) {
                int sum = carry;
                if(i >=0)
                    sum += Character.getNumericValue(x.charAt(i));
                if(j>=0)
                    sum += Character.getNumericValue(y.charAt(j));
                output.append(sum%10);
                carry = sum / 10;
                i--;
                j--;
            }
            output = output.reverse();
            return output.toString();
        }
    }
    

Log in to reply
 

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