【算法-Java】给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法-Java】给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1503字，纯文字阅读大概需要3分钟。

内容图文

一、示例

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

二、说明

1. 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
2. 例如：“0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效的 IP 地址。

三、Demo

public class Solution {
    public static void main(String[] args) {
        String s = "101023";
        System.out.println(Solution.restoreIpAddresses(s));
    }

    // cur: 当前答案,以List<String>的形式,最后再join成String形式,例如[[255],[255],[111],[35]] -> 255.255.111.35
    // pos: 当前扫描到的s的位置
    // ans: 最终答案
    public static void backtracking(String s, int pos, List<String> cur,  List<String> ans) {
        // [[255],[255],[111],[35]] List<String>长度 = 4
        if (cur.size() >= 4) {
            if (pos == s.length()) {
                ans.add(String.join(".", cur));
            }
            return;
        }
        // 分割得到ip地址的一段后,下一段只能在长度1-3范围内选择
        for (int i = 1; i <= 3; i++) {
            if (pos+i > s.length()) {
                break;
            }
            String segment = s.substring(pos, pos+i);
            // 剪枝条件：不能以0开头，不能大于255
            if (segment.startsWith("0") && segment.length() > 1 || (i == 3 && Integer.parseInt(segment) > 255)) {
                continue;
            }
            cur.add(segment);
            // 注意此处传的参数
            backtracking(s, pos+i, cur, ans);
            cur.remove(cur.size()-1);
        }
    }
    public static List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        backtracking(s, 0, new ArrayList<>(), ans);
        return ans;
    }
}

内容总结

以上是互联网集市为您收集整理的【算法-Java】给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。全部内容，希望文章能够帮你解决【算法-Java】给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---