题目：

93. 复原IP地址

题解：

思路:

我们要知道IP的格式,每位是在0~255之间,

注意: 不能出现以0开头的两位以上数字,比如012,08...

思路一:暴力法

我们把所有出现可能都列举出来,看是否满足条件.

思路二:回溯算法

代码：

1. 代码一：（思路一）

/** * code93 */
import java.util.*;

public class code93 {

    public static List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        int n = s.length();
        for (int i = 0; i < 3; i++) {
            for (int j = i + 1; j < i + 4; j++) {
                for (int k = j + 1; k < j + 4; k++) {
                    if (i < n && j < n && k < n) {
                        String tmp1 = s.substring(0, i + 1);
                        String tmp2 = s.substring(i + 1, j + 1);
                        String tmp3 = s.substring(j + 1, k + 1);
                        String tmp4 = s.substring(k + 1);
                        if (helper(tmp1) && helper(tmp2) && helper(tmp3) && helper(tmp4)) {
                            res.add(tmp1 + "." + tmp2 + "." + tmp3 + "." + tmp4);
                        }
                    }
                }
            }
        }
        return res;
    }

    public static boolean helper(String tmp) {
        if (tmp == null || tmp.length() == 0 || tmp.length() > 3 || (tmp.charAt(0) == '0' && tmp.length() > 1)
                || Integer.parseInt(tmp) > 255) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        String str = "25525511135";
        List<String> list = restoreIpAddresses(str);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));			            
        }
    }
}

2. 代码二：（思路二）

/** * code93 */
import java.util.*;

public class code93 {

    // 解法二：
    public static List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        int n = s.length();
        backtrack(0, "", 4, s, res, n);// flag == 4, 表示 IP地址分为 4 段
        return res;
    }

    public static void backtrack(int i, String tmp, int flag, String s, List<String> res, int n) {
        if (i == n && flag == 0) {
            res.add(tmp.substring(0, tmp.length() - 1));// 最后加了个"." 要去掉
            return;
        }
        if (flag < 0) {
            return;
        }
        for (int j = i; j < i + 3; j++) {
            if (j < n) {
                if (i == j && s.charAt(j) == '0') {
                    backtrack(j + 1, tmp + s.charAt(j) + ".", flag - 1, s, res, n);
                    break;
                }
                if (Integer.parseInt(s.substring(i, j + 1)) <= 255) {
                    backtrack(j + 1, tmp + s.substring(i, j + 1) + ".", flag - 1, s, res, n);
                }
            }
        }
    }

    public static void main(String[] args) {
        String str = "25525511135";
        List<String> list = restoreIpAddresses(str);
        for (int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
        }
    }
}

参考：

1. 暴力 和 回溯
2. 复原IP地址
3. 可能是最优美的暴力解法了
4. 简单易于理解的回溯法【Java】
5. 关于JAVA中字符串函数subString()的用法
6. Java中List集合的遍历
7. java中如何遍历ArrayList集合中的元素并输出