My code in Java


  • 174
    F
    public class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> res = new ArrayList<String>();
            int len = s.length();
            for(int i = 1; i<4 && i<len-2; i++){
                for(int j = i+1; j<i+4 && j<len-1; j++){
                    for(int k = j+1; k<j+4 && k<len; k++){
                        String s1 = s.substring(0,i), s2 = s.substring(i,j), s3 = s.substring(j,k), s4 = s.substring(k,len);
                        if(isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)){
                            res.add(s1+"."+s2+"."+s3+"."+s4);
                        }
                    }
                }
            }
            return res;
        }
        public boolean isValid(String s){
            if(s.length()>3 || s.length()==0 || (s.charAt(0)=='0' && s.length()>1) || Integer.parseInt(s)>255)
                return false;
            return true;
        }
    }
    

    3-loop divides the string s into 4 substring: s1, s2, s3, s4. Check if each substring is valid.
    In isValid, strings whose length greater than 3 or equals to 0 is not valid; or if the string's length is longer than 1 and the first letter is '0' then it's invalid; or the string whose integer representation greater than 255 is invalid.


  • 0
    C

    Nice code, thanks!


  • 0
    A

    In this case, non-DP solution seems to be much better than DP, considering the corner cases like '0' in front of other digits, a bunch of string / integer conversions and string appending.


  • 1
    E

    good comment
    nice code and easy to understand


  • 1
    F

    nice code, practice a DFS version based on your idea.

    bool isValidIp(string s) {
        if (s.length() > 1 && s[0] == '0') {
            return false;
        }
        
        int num = stoi(s);
        return (num <= 255 && num >= 0);
    }
    
    void dfs(string s, int pos, int index, string &output, vector<string> &result) {
        if (pos == 4) {
            string ip = s.substr(index);
            if (isValidIp(ip)) {
                output.append(ip);
                result.push_back(output);
            }
            return;
        }
        
        for (int i = 1; s.length() - index - i >= (4 - pos) && i < 4; i++) {
            string ip = s.substr(index, i);
            if (isValidIp(ip)) {
                int oriSize = output.length();
                output.append(ip).append(".");
                dfs(s, pos + 1, index + i, output, result);
                output.resize(oriSize);
            }
        }
    }
    
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        if (s.length() < 4 || s.length() > 12) {
            return result;
        }
        string output;
        dfs(s, 1, 0, output, result);
        return result;
    }

  • 3
    H

    My backtrack solution, use int set to eliminate some cases.

    public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        if(s.length() < 4 || s.length() > 12)
            return result;
        restoreIpAddresses(s, 0, 4, result, new StringBuilder());
        return result;
    }
    public void restoreIpAddresses(String s, int index, int set, List<String>result, StringBuilder sb){
        if(index > s.length() || s.length() - index < set ||s.length() - index > set*3){
            return;
        }else if(index == s.length()){
            sb.setLength(sb.length()-1);
            result.add(sb.toString());
            return;
        }
        int len = sb.length();
        for(int i = 1; i <=3 ; i++){
            if(index+i <= s.length() && 
               (i!=3 || Integer.parseInt(s.substring(index, index+i))< 256) &&
               (i==1 || Integer.parseInt(s.substring(index, index+1))!= 0)) 
            {
                sb.append(s.substring(index, index+i)+".");
                restoreIpAddresses(s, index+i, set-1, result, sb);
                sb.setLength(len);
            }
        }
    }
    

    }


  • 4
    V

    Thanks, same idea using c++.

    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        int len = s.size();
        for(int i=1; i<4 && i<len-2; i++){
            for(int j=i+1; j<i+4 && j<len-1; j++){
                for(int k=j+1; k<j+4 && k<len; k++){
                    if(len-k>3)
                        continue;
                    string a = s.substr(0, i);
                    string b = s.substr(i, j-i);
                    string c = s.substr(j, k-j);
                    string d = s.substr(k, len-k);
                    if(isValid(a) && isValid(b) && isValid(c) && isValid(d))
                        res.push_back(a+'.'+b+'.'+c+'.'+d);
                }
            }
        }
        return res;
    }
    bool isValid(string s){
        if(atoi(s.c_str()) > 255 || s[0] == '0' && s.size() > 1)
            return false;
        return true;
    }

  • 1
    K

    s.length()>3 || s.length()==0 seems unnecessary


  • 0
    P

    is this not brute force method?


  • 0
    B

    @Kenigma, What if s4 contains 0 character, or s4 contains more than 3 characters?


  • 0
    D

    @pustar I think it is brute force. But DFS is also brute force. Since there are only four numbers, so at most three nested for loops, I think this way is acceptable, and more readable.


  • 0
    Z

    It is somehow difficult to generalize to other situation. Considering a much longer string(containing only digits) and an integer N, now I want to split the string into N pieces, and each piece should within the range [0, 255].


  • 0
    G

    @Kenigma , I also think "s.length()>3 || s.length()==0 " is unnecessary. Because i<4, j<i+4,k<j+4 already guarantee the length of s. But the result is wrong if I remove these 2 statements. Anyone tell me why?


  • 1
    M

    @goodbyenwp : Its to validate the length of the 4th string s4


  • 13

    Thanks for your sharing. But I think DFS is more elegant and concise.

        public List<String> restoreIpAddresses(String s) {
            List<String> result = new ArrayList<>();
            doRestore(result, "", s, 0);
            return result;
        }
        
        private void doRestore(List<String> result, String path, String s, int k) {
            if (s.isEmpty() || k == 4) {
                if (s.isEmpty() && k == 4)
                    result.add(path.substring(1));
                return;
            }
            for (int i = 1; i <= (s.charAt(0) == '0' ? 1 : 3) && i <= s.length(); i++) { // Avoid leading 0
                String part = s.substring(0, i);
                if (Integer.valueOf(part) <= 255)
                    doRestore(result, path + "." + part, s.substring(i), k + 1);
            }
        }
    

  • 0
    J

    @Kenigma s.length()>3 is necessary. It is used to validate the last string. Since it could be far more than 3 digits, Integer.parseInt(str) will throw an exception if the str is too long (out of the range of integer).


  • 0

    @cdai

    your code is not DFS . maybe is Violent enumeration


  • 0
    S
    This post is deleted!

  • 0
    S

    My C# version

    public class Solution {
        public IList<string> RestoreIpAddresses(string s) 
        {
            var result = new List<string>();
            if(s==null || s.Length < 4)
                return result;
            for(int i = 1; i<4 && i+3 <=s.Length; i++)
                for(int j = 1; j<4 && i+j+2<=s.Length; j++)
                    for(int k = 1; k<4 && i+j+k+1<=s.Length; k++)
                    {
                        var array = new []{s.Substring(0,i), s.Substring(i,j), s.Substring(i+j, k), s.Substring(i+j+k)};
                        if(array.All(n=>IsValid(n)))
                        {
                            result.Add(string.Join(".", array));
                        }
                    }
            return result;
        }
        
        private bool IsValid(string str)
        {
            if(string.IsNullOrEmpty(str) || str.Length > 3 || (str[0]=='0'&&str.Length>1) ||int.Parse(str)>255 || int.Parse(str)<0)
                return false;
            return true;
        }
    }
    

  • 0
    T
    This post is deleted!

Log in to reply
 

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