面试算法87:恢复IP地址

2024-01-03 12:45:21

题目

输入一个只包含数字的字符串,请列出所有可能恢复出来的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');
    }
}

文章来源:https://blog.csdn.net/GoGleTech/article/details/135360360
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。