Very simple DFS solution


  • 70
    G
    public List<String> restoreIpAddresses(String s) {
        List<String> solutions = new ArrayList<String>();
        restoreIp(s, solutions, 0, "", 0);
        return solutions;
    }
    
    private void restoreIp(String ip, List<String> solutions, int idx, String restored, int count) {
        if (count > 4) return;
        if (count == 4 && idx == ip.length()) solutions.add(restored);
        
        for (int i=1; i<4; i++) {
            if (idx+i > ip.length()) break;
            String s = ip.substring(idx,idx+i);
            if ((s.startsWith("0") && s.length()>1) || (i==3 && Integer.parseInt(s) >= 256)) continue;
            restoreIp(ip, solutions, idx+i, restored+s+(count==3?"" : "."), count+1);
        }
    }

  • 0
    W
    This post is deleted!

  • 0
    T
    This post is deleted!

  • 0
    M

    is the time complexity O(3^n)?


  • 0
    D

    i think you should delete "i==3 && " and replace the "continue" with"break"or or change these two"break" to"return"


  • 1
    V

    You can try by deleting "i==3" and it will cost one more ms. The reason is you only need to check i == 3 rather than Integer.parseInt(s) >= 256 when i < 3. But replace break and continue with return is a good idea.


  • 1
    I

    It should be O(3^4), which means it should be constant.


  • 1
    Y

    Neat solution! Thanks!

    Another implementation with minor modifications.

    /*  Requirements of IP adresses:
     *  (1) No section can start with a 0 expect 0 itself
     *  (2) No section can exceed 256
     *  (3) Have to have exactly 4 sections
     */ 
    public List<String> restoreIpAddresses(String s) {
        List<String> ips = new ArrayList<>();
        char[] arr = s.toCharArray();
        restoreIpAddresses(arr, 0, new StringBuilder(), ips, 0);
        return ips;
    }
    
    private void restoreIpAddresses(char[] arr, int startIdx, StringBuilder ip, List<String> ips, int count){
        if(count > 4) return;
        if(count == 4){
            if(startIdx == arr.length){
                ips.add(ip.toString());
            }
            return;
        }
        
        int num = 0, ipLen = ip.length();
        for(int i = startIdx; i <= startIdx+3 && i < arr.length; i++){
            num = num*10 + arr[i]-'0';
            if(num >= 256) break;
            
            ip.append(num);
            if(count != 3) ip.append('.'); // the last section should not append '.'
            restoreIpAddresses(arr, i+1, ip, ips, count+1);
            ip.setLength(ipLen);
            
            if(num == 0) break; // if num starts with 0, only allows a single 0
        }
    }

  • 0
    P

    great-------------------------------------------------


  • 0
    Y

    @dj814113652
    It is a good idea to replace continue with break.
    But I disagree with you idea that i == 3 && should be deleted. Because in the case where i < 3, the number has at most two digits, which is definitely less than 255. This means there is no need to convert the number into an integer with Integer.parseInt(s). In this sense, i == 3 && short-circuits the expression to the right.


  • 1
    public List<String> restoreIpAddresses(String s) {
       List<String> list = new ArrayList();
       if(s.length() > 12) return list;
         
       helper(s, list, 0, "", 0);  
       return list;
     }
     
     void helper(String s, List<String> list, int pos, String res, int sec){
       if(sec == 4 && pos == s.length()) {
         list.add(res);
         return;
       }  
         
       for(int i = 1; i <= 3; i++){
         if(pos + i > s.length()) break;  
         String section = s.substring(pos, pos + i);
         if(section.length() > 1 && section.startsWith("0") || Integer.parseInt(section) >= 256)  break;
         helper(s, list, pos + i, sec == 0 ? section : res + "." + section, sec + 1);
       }  
     }

  • 0
    H

    C++ solution based on your idea

    class Solution {
    public:
        vector<string> restoreIpAddresses(string s) {
            
            vector<string> ret;
            helper(s, ret, 0, "", 0);
            return ret;
        }
        
        
        
        
        void helper(string s, vector<string> &ret, int index, string current, int count) {
            
            if (count > 4) return;
            if (count == 4 && index == s.size()) { ret.push_back(current); return;}
            
            for(int i = 1; i < 4; i++) {
                if ((index + i) > s.size()) break;
                string temp = s.substr(index,i);
                if (((temp[0] == '0') && (temp.size() > 1)) || ((i == 3) && (stoi(temp) > 255))) continue;
                helper(s, ret, index+i, current + temp + (count == 3 ? "" : "."), count+1);
            }
        }
    };
    

  • 0
    K

    Such a wonderful approach...Thanks


Log in to reply
 

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