LeetCode - Restore IP Addresses | Darren's Blog

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example: given "25525511135", return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
Note: according to the feedback from the test cases, any part that is in the form of '0x' or '0xx' is not valid.
Recursion: Using DFS from http://blog.csdn.net/u011095253/article/details/9158449

0-255的数字，转换成字符，即每个Part 可能由一个字符组成，二个字符组成，或者是三个字符组成。那这又成为组合问题了，dfs便呼之欲出

所以我们写一个For循环每一层从1个字符开始取一直到3个字符，再加一个isValid的函数来验证取的字符是否是合法数字，如果是合法的数字，我们再进行下一层递归，否则跳过。

public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> res = new ArrayList<String>();
        if (s.length()<4||s.length()>12) return res;
        dfs(s,"",res,0);
        return res;
    }
   
    public void dfs(String s, String tmp, ArrayList<String> res, int count){
        if (count == 3 && isValid(s)) {
            res.add(tmp + s);
            return;
        }
        for(int i=1; i<4 && i<s.length(); i++){
            String substr = s.substring(0,i);
            if (isValid(substr)){
                dfs(s.substring(i), tmp + substr + '.', res, count+1);
            }
        }
Iterative Version: code from http://www.darrensunny.me/leetcode-restore-ip-addresses/
Alternatively, we can consider each part iteratively by explicitly determining the positions of the dots.

public ArrayList<String> restoreIpAddresses(String s) {

        ArrayList<String> result = new ArrayList<String>();

        if (s == null)

            return result;

        int n = s.length();

        if (n < 4 || n > 12)

            return result;

 

        // For each possible first part

        for (int i = 1; i <= 3; i++) {      // At most three digits at each part

            if (n-i > 9)    // The number of digits for remaining three parts should not exceed 9

                continue;

            if (s.charAt(0) == '0' && i > 1)    // 0x or 0xx is not allowed

                break;

            String first = s.substring(0, i);   // String before the first dot

            if (Integer.parseInt(first) <= 255) {   // The first part is within proper range

                // For each possible second part given the first part

                for (int j = i+1; j <= i+3 && j < n; j++) {

                    if (n-j > 6)    // The number of digits for remaining two parts should not exceed 6

                        continue;

                    if (s.charAt(i) == '0' && j > i+1)

                        break;

                    String second = s.substring(i, j);  // String after the first dot and before the second

                    if (Integer.parseInt(second) <= 255) {  // The second part is within proper range

                        // For each possible third part given the second part

                        for (int k = j+1; k <= j+3 && k < n; k++) {

                            if (n-k > 3)    // The number of digits for remaining part should not exceed 3

                                continue;

                            if (s.charAt(j) == '0' && k > j+1)

                                break;

                            String third = s.substring(j, k);   // String after the second dot and before the third

                            if (Integer.parseInt(third) <= 255) {   // The third part is within proper range

                                // If the fourth part is a single digit, or it does not begin with a '0' and

                                // it is within proper range, we have got a valid IP address

                                if (k == n-1 || s.charAt(k) != '0' && Integer.parseInt(s.substring(k)) <= 255)

                                    result.add(first+'.'+second+'.'+third+'.'+s.substring(k));

                            }

                        }

                    }

                }

            }

        }

 

        return result;

    }

Also refer to http://yucoding.blogspot.com/2013/04/leetcode-question-83-restore-ip.html
Read full article from LeetCode - Restore IP Addresses | Darren's Blog