simple standard java solution with backtracking


  • 0
    C
    public List<String> restoreIpAddresses(String s) {
            if(s.length() < 4 || s.length() > 12) return new ArrayList<String>();
            List<String> result = new ArrayList<String>();
            helper(1, s, new String(), result);
            return result;
        }
        private void helper(int layer, String s, String curr, List<String> result){
            if(layer == 5 && curr.length() == s.length()+3) result.add(new String(curr));
            else{
                if(s.length() - (curr.length() - layer + 1)> (5-layer) * 3) return;
                int len = curr.length() - layer + 1;
                for(int i=len;i-len<3 && i<s.length();i++){
                    String temp = new String(curr);
                    String toAdd = s.substring(len, i+1);
                    if(Integer.parseInt(toAdd) > 255 || (toAdd.length() > 1 && toAdd.charAt(0)=='0')) return;
                    if(layer < 4)
                        curr += toAdd + ".";
                    else
                        curr += toAdd;
                    helper(layer+1, s, curr, result);
                    curr = temp;
                }
            }
        }
    

Log in to reply
 

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