$$\color{Red}{复原IP地址【leetcode93 dfs搜索合法分隔数字】}$$

我的网站=> 分享了我关于前后端的各种知识和生活美食~

我于Acwing平台分享的零散刷的各种各样的题

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和"192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

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

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

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

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

解析

这道题不是难题，但是提供了线性遍历排除前导零的搜索方法。

即根据标志位确定枚举了多少组，然后根据当前组枚举的首位和指针位置，如果不是第一位，且第一位是 0 的情况下，直接跳出，即存在前导零。

而剪枝是一个自然能想到的，即枚举 3位 的情况下，如果后面未枚举的数字数量超过 3个字符，说明非法。

class Solution {

    public static List<String> ans = new ArrayList<>();

    public static void dfs(String s, int u, int k, String path) {
        // 剪枝优化
        if (k == 3 && s.length() - u > 3) {
            return;
        }
        // 答案存储
        if (k == 4) {
            if (u == s.length()) ans.add(path.substring(0, path.length() - 1));
            return;
        }
        // dfs 搜索
        for (int i = u, t = 0; i < s.length(); i ++) {
            // 前导0去除
            if (i > u && s.charAt(u) == '0') break;
            t = 10 * t + s.charAt(i) - '0';
            // 合法数字判断
            if (t > 255) break;
            dfs (s, i + 1, k + 1, path + t + ".");
        }
    }

    public List<String> restoreIpAddresses(String s) {
        ans.clear();
        dfs(s, 0, 0, "");
        return ans;
    }
}