Very simple DFS solution


  • 71
    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.


  • 2
    I

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


  • 2
    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.


  • 0

    这道题也是一个用DFS找所有的可能性的问题。这样一串数字:25525511135
    我们可以对他进行切分,但是根据IP的性质,有些切分就是明显不可能的:
    比如011.11.11.11, 这个的问题是以0开头了,不合法,直接跳过。
    比如257.11.11.11, 257大于IP里的最大数 255了,不合法,直接跳过。
    然后我们把这一层切分后剩下的字符串传到下一层,继续去找。
    直到最后我们得到4个section为止,把这个结果存到我们的result list。

    This question is also a question of using DFS to find all possibilities. Such a string of numbers: 25525511135
    We can divide it, but depending on the nature of the IP, it is obviously impossible to divide some of cases:
    For example, 011.11.11.11, the problem is to 0 at the beginning, not legitimate, directly skipped.
    For example, 257.11.11.11, 257 is greater than the maximum number of 255, illegal, skip directly.
    Then we pass the rest of the string to the next layer, continue to find.
    Until the end we got 4 sections, put this result in our result list.

    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


  • 0
    F

    @greatgrahambini Could you please explain what you are doing in the for loop ? Thanks in advance


  • 0
    F

    @Jerry Hi Jerry, can you briefly explain the two lines in the for loop ? I am lost. Thank you


  • 0
    X

    @IanWalker0421
    I think it should be 3^3, since if the first three section is determined, the number value for the last section is fixed. But either way, it is constant.


  • 0
    A

    @xiangyu6 No, it should still be O(3^4), because although the fourth section is determined, the recursion still goes on to check the validity of the fourth section (i.e. it still divides the fourth section in 3 different ways).


Log in to reply
 

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