面试算法87：恢复IP地址

题目

输入一个只包含数字的字符串，请列出所有可能恢复出来的IP地址。例如，输入字符串"10203040"，可能恢复出3个IP地址，分别为"10.20.30.40"、“102.0.30.40"和"10.203.0.40”。

分析

首先总结IP地址的特点。一个IP地址被3个’.'字符分隔成4段，每段是从0到255之间的一个数字。另外，除"0"本身外，其他数字不能以’0’开头。例如，"10.203.0.40"是一个有效的IP地址，但"10.203.04.0"却不是有效的IP地址，这是因为第3个数字"04"以’0’开头。
下面逐个扫描输入字符串中的字符以恢复IP地址。针对字符串中的每个数字，通常面临两个选项。第1个选项是将当前字符拼接到当前分段数字的末尾，拼接之后的数字应该在0到255之间。第2个选项是当前字符作为一个新的分段数字的开始。需要注意的是，一个IP地址最多只有4个分段数字，并且当开始一个新的分段数字时前一个分段数字不能是空的。
如果输入的字符串的长度为n，由于逐一处理字符串中的每个字符，因此需要n步，并且每一步都面临两个可能的选项。

解

public class Test {
    public static void main(String[] args) {
        List<String> result = restoreIpAddresses("10203040");
        for (String item : result) {
            System.out.println(item);
        }
    }

    public static List<String> restoreIpAddresses(String s) {
        List<String> result = new LinkedList<>();
        helper(s, 0, 0, "", "", result);

        return result;
    }

    // i: 字符串s中当前被处理的字符的下标
    // segI: 当前分段数字的下标，由于IP地址有4个分段数字，因此参数segI的取值范围是从0到3。
    // ip: 当前已经恢复的IP地址
    private static void helper(String s, int i, int segI, String seg, String ip, List<String> result) {
        if (i == s.length() && segI == 3 && isValidSeg(seg)) {
            result.add(ip + seg);
        }
        else if (i < s.length() && segI <= 3) {
            char ch = s.charAt(i);
            if (isValidSeg(seg + ch)) {// 拼接字符串，不新建分段
                helper(s, i + 1, segI, seg + ch, ip, result);
            }

            if (seg.length() > 0 && segI < 3) {// 新建分段
                helper(s, i + 1, segI + 1, "" + ch, ip + seg + ".", result);
            }
        }
    }

    private static boolean isValidSeg(String seg) {
        return Integer.valueOf(seg) <= 255 && (seg.equals("0") || seg.charAt(0) != '0');
    }
}