my solution with combination sum


  • 0
    L
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        if (s.length()>12){
            return ans;
        }
        List<List<Integer>> splices =new ArrayList<>();
        helper(s.length(), new ArrayList<>(), splices);
        for (List<Integer> splice : splices){
            int sum=0;
            StringBuffer sb = new StringBuffer();
            for (Integer i: splice){
                String ss = s.substring(sum, sum+i);
                if (ss.startsWith("0") && ss.length()!=1){
                    break;
                }
                if (Integer.parseInt(ss) >255){
                    break;
                }
                sb.append(s.substring(sum, sum+i)).append(".");
                sum+=i;
            }
            if (sb.length()==s.length()+4){
                ans.add(sb.substring(0, sb.length()-1));
            }
        }
        return ans;        
    }
    
    private void helper(int target, List<Integer> list, List<List<Integer>> ret){
        if (target==0 && list.size()==4){
            ret.add(list);
            return;
        }
        for (int i=1;i<=3;i++){
            int nt = target-i;
            if (nt >=0){
                List<Integer> copy = new ArrayList<>(list);
                copy.add(i);
                helper(nt, copy, ret);
            }else {
                break;
            }
        }
    }

Log in to reply
 

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