My java backtracking method, dealing with over flow and '0'


  • 0

    I deal with '0' using pruning. When I meet over flow, for example, if there are three numbers 233 , 4 , 5, because len = Math.max("233".length() , "4".length()) == 3, len < "5".length(), so 233 , 4 , 5 can't be a result.
    hope it helps~

    public class Solution {
        public boolean isAdditiveNumber(String num) {
            if(num == null || num.length() == 0) {
                return true;
            }
            List<String> list = new ArrayList<String>();
            return dfshelper(num , 0 , list);
        }
        
        protected boolean dfshelper(String num , int start , List<String> list) {
            if(start == num.length()) {
                if(list.size() >= 3) {
                    return true;
                }else {
                    return false;
                }
            }
            for(int i = start ; i < num.length() ; i++) {
                if(num.charAt(start) == '0' && i > start) continue;
                if(list.size() >= 2) {
                    int len = Math.max(list.get(list.size() - 1).length() , list.get(list.size() - 2).length());
                    if(len > num.length() - start) return false;//dealing with over flow.
                }
                String s = num.substring(start , i + 1);
                if(list.size() <= 1) {
                    list.add(s);
                    if(dfshelper(num , i+1 , list)) return true;
                    list.remove(list.size() - 1);
                }else {
                    long n1 = Long.parseLong(list.get(list.size() - 1));
                    long n2 = Long.parseLong(list.get(list.size() - 2));
                    if(n1 + n2 == Long.parseLong(s)) {
                        list.add(s);
                        if(dfshelper(num , i+1 , list)) return true;
                        list.remove(list.size() - 1);
                    }
                }
            }
            return false;
        }
    }

Log in to reply
 

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