LeetCode 93. 复原 IP 地址

约 5 分钟
文章信息 25 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 历史考题 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 华为 拼多多 网易 小米 商汤 旷视 亚马逊 虾皮 小红书 作业帮
标签
字符串 回溯 回溯经典题
目录

题目描述

✅ 93. 复原 IP 地址

考察公司：作业帮

考察时间：2025.5.27

image-20250510084624253

题意分析

输入一个只含数字的字符串，要求在其中插入三个点，把它切成四段，输出所有能构成合法 IPv4 地址的切法。字符串本身不能重排、不能增删字符，只能决定「在哪里切」。

「合法」由三条规则共同定义，缺一条都会做错：

  • 数值范围：每段解释成十进制数后必须落在 0 到 255 之间；
  • 无前导零：除了单独的 "0"，任何段都不能以 0 开头，"01"、"00"、"010" 全部非法；
  • 恰好四段且用完全部字符：不能少切、不能多切，也不能剩下任何字符没有归入某一段。

约束透露的信号很强：每段长度只能是 1 到 3，四段加起来总长只能落在 4 到 12 之间，所以有效输入的规模天然被钉死在一个极小的区间里；而题目要的是「所有可能的结果」，不是判断存在性，也不是求最优解——这意味着必须把每一种切法都考虑到，漏一种就是错。

需要提前想清楚的边界：长度小于 4 或大于 12 的输入直接无解；"0000" 有唯一答案 "0.0.0.0"，说明前导零规则不能把单独的 "0" 一起拒掉；"010010" 这类含 0 的输入是前导零规则的试金石；可能存在合法切法为零的输入，此时应返回空列表而不是报错。

解法：回溯枚举每段

核心思路

从左到右依次确定 4 个 IP 段，每段只尝试 1 到 3 位。选择前检查前导零和数值上限，并根据“剩余字符是否能装入剩余段”提前剪枝；凑满 4 段且恰好用完字符串时收集答案。

解题步骤

  • 递归状态记录当前下标和已选段。
  • 若剩余字符少于剩余段数，或多于其 3 倍，直接返回。
  • 当前段逐位构造数值；出现前导零或数值超过 255 时停止扩展。
  • 选择当前段后递归，返回时撤销；4 段正好用完字符时记录结果。

代码实现

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> answer = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), answer);
        return answer;
    }

    private void backtrack(String s, int start, List<String> parts, List<String> answer) {
        if (parts.size() == 4) {
            if (start == s.length()) {
                answer.add(String.join(".", parts));
            }
            return;
        }

        int chars = s.length() - start;
        int segments = 4 - parts.size();
        if (chars < segments || chars > segments * 3) {
            return;
        }

        int value = 0;
        for (int end = start; end < s.length() && end < start + 3; end++) {
            if (end > start && s.charAt(start) == '0') {
                break;
            }
            value = value * 10 + s.charAt(end) - '0';
            if (value > 255) {
                break;
            }

            parts.add(s.substring(start, end + 1));
            backtrack(s, end + 1, parts, answer);
            parts.remove(parts.size() - 1);
        }
    }
}

func restoreIpAddresses(s string) []string {
    answer := make([]string, 0)
    parts := make([]string, 0, 4)

    var backtrack func(int)
    backtrack = func(start int) {
        if len(parts) == 4 {
            if start == len(s) {
                answer = append(answer, parts[0]+"."+parts[1]+"."+parts[2]+"."+parts[3])
            }
            return
        }

        chars, segments := len(s)-start, 4-len(parts)
        if chars < segments || chars > segments*3 {
            return
        }

        value := 0
        for end := start; end < len(s) && end < start+3; end++ {
            if end > start && s[start] == '0' {
                break
            }
            value = value*10 + int(s[end]-'0')
            if value > 255 {
                break
            }

            parts = append(parts, s[start:end+1])
            backtrack(end + 1)
            parts = parts[:len(parts)-1]
        }
    }

    backtrack(0)
    return answer
}

复杂度分析

  • 时间复杂度：$O(1)$，固定 4 层、每层最多 3 个选择，搜索规模至多为常数级。
  • 空间复杂度：$O(1)$，递归深度和路径长度都固定为 4；不计返回结果。

关键点总结

  • 合法段的长度为 1 到 3，数值范围为 0 到 255。
  • 单独的 "0" 合法，多位段不能以 0 开头。
  • 剩余字符必须满足 segments <= chars <= 3 * segments。
  • 收集答案时既要凑满 4 段，也要恰好用完所有字符。

易错点总结

  • 只判断数值会误收 "01"、"00" 等带前导零的段。
  • 凑满 4 段后若不检查字符串是否用完，会产生残缺结果。
  • 递归返回后必须撤销当前段，避免不同分支互相污染。

相似题目

题目 难度 考察点
LCR 087. 复原 IP 地址 中等 与本题完全同题，适合换一门语言或换一种写法自测
131. 分割回文串 中等 同为切分字符串的回溯，但段数不固定，合法性判据换成回文
306. 累加数 中等 只需枚举前两段、其余由加法递推唯一确定，前导零规则与本题一致
468. 验证IP地址 中等 不做搜索只做校验，还要同时兼容 IPv6，考规则细节的完备性
140. 单词拆分 II 困难 切分方案数不再有常数上界，回溯之上还要靠记忆化控制爆炸
751. IP 到 CIDR 中等 反向问题：从起始 IP 生成网段，考 IP 与整数互转及位运算