LeetCode LCR 087. 复原 IP 地址

约 6 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
字符串 LCR 回溯

题目描述

✅ LCR 087. 复原 IP 地址

image-20260929010041329

image-20260929010041332

题意分析

在数字字符串中插入三个点，得到恰好四段的 IPv4 地址。所有字符必须按原顺序用完，每段数值在 0 到 255 之间，只有单独的零允许以零开头。

每个合法段只能有一到三位，因此可以从左到右枚举每段长度。四段总共只能覆盖四到十二个字符，范围之外一定无解；官方题面允许空串以及最长 3000 个字符的输入，不能假定字符串本身已经适合构成地址。

解法：按四段约束回溯

核心思路

[!blue]

dfs(i) 表示 s[0..i-1] 已经切成 t 中的若干合法段，下一段从 i 开始。始终保持各段拼接后恰好覆盖此前的字符，递归到 j+1 才能让下一段与当前段相邻而不重叠。

成功必须同时满足字符用完和已有四段。只用完字符但段数不足，或已有四段却还剩字符，都不能形成地址，应直接返回。代码先检查成功，再检查这两类无法继续的状态，因此不会把完整答案提前拦掉。

从起点 i 开始最多取三位作为当前段，段尾 j 不能越过串尾。x 保存 s[i..j] 的数值，每延长一位就执行 x = x*10 + digit，可以增量判断数值范围。

若 x > 255，继续追加数字只会使数值更大；若首字符为零且段长已超过一，再延长仍然带前导零。这两种失败都不可能通过延长修复，所以用 break 排除后面所有更长候选；单独的零仍能进入递归。

每次只选合法段，所以成功分支一定是有效地址；任意有效地址的各段长度都在枚举范围内，也不会被上述剪枝排除，因此不会漏解。不同分段边界确定不同的点号位置，不会重复生成同一个地址。成功时拼接为新字符串，回溯撤销最后一段不会改变已保存的结果。

解题步骤

  1. 从起点零和空段列表开始递归。
  2. 字符已用完且恰好四段时，用点号连接各段并保存；只满足其中一项时返回。
  3. 从当前起点尝试一到三位，增量计算段值，遇到超限或多位前导零就停止延长。
  4. 将合法段加入路径，递归处理后缀，再撤销这一段。

代码实现

class Solution {
    private int n;
    private String s;
    private List<String> answer = new ArrayList<>();
    private List<String> t = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        n = s.length();
        this.s = s;
        dfs(0);

        return answer;
    }

    // i：当前待切分段的起点，s[0..i-1] 已切成 t 中的若干合法段。
    private void dfs(int i) {
        // 字符用完且恰好四段，才是答案。
        if (i >= n && t.size() == 4) {
            answer.add(String.join(".", t));

            return;
        }

        // 字符用完但段数不足，或段数已满但字符没用完，都无解。
        if (i >= n || t.size() >= 4) {
            return;
        }

        int x = 0;

        // 段长最多 3，同时不越界。
        for (int j = i; j < Math.min(i + 3, n); ++j) {
            x = x * 10 + s.charAt(j) - '0';

            // 超过 255 或出现前导零后，继续延长只会更糟，直接 break。
            if (x > 255 || (s.charAt(i) == '0' && i != j)) {
                break;
            }

            t.add(s.substring(i, j + 1));
            dfs(j + 1);
            t.remove(t.size() - 1);
        }
    }
}

import (
    "strings"
)

func restoreIpAddresses(s string) (answer []string) {
    n := len(s)
    t := []string{}

    // i：当前待切分段的起点，s[0..i-1] 已切成 t 中的若干合法段。
    var dfs func(int)
    dfs = func(i int) {
        // 字符用完且恰好四段，才是答案。
        if i >= n && len(t) == 4 {
            answer = append(answer, strings.Join(t, "."))
            return
        }
        // 字符用完但段数不足，或段数已满但字符没用完，都无解。
        if i >= n || len(t) == 4 {
            return
        }
        x := 0
        // 段长最多 3，同时不越界。
        for j := i; j < i+3 && j < n; j++ {
            x = x*10 + int(s[j]-'0')
            // 超过 255 或出现前导零后，继续延长只会更糟，直接 break。
            if x > 255 || (j > i && s[i] == '0') {
                break
            }
            t = append(t, s[i:j+1])
            dfs(j + 1)
            t = t[:len(t)-1]
        }
    }
    dfs(0)
    return
}

复杂度分析

  • 时间复杂度：$O(1)$。最多选择四段，每段至多尝试三种长度，搜索树规模受 $3^4$ 限制；每个结果最多包含十二位数字和三个点。即使输入很长，代码也只搜索有限的前缀，四段后仍有字符就返回。
  • 空间复杂度：不计输出为 $O(1)$。递归深度最多五层，路径最多保存四个长度不超过三的段。

关键点总结

[!green]

  • 段值合法、没有多位前导零、恰好四段、原字符串用完，四项条件缺一不可。
  • 数值超限和前导零都会随延长持续失效，因此可以直接结束本层的后续枚举。
  • 长度不在四到十二之间时没有答案，现有段长和段数限制也会自然返回空结果，不需要扫描完整长串。

易错点总结

[!yellow]

  • 必须恰好四段且全部字符用完，不能只检查其中一个条件。
  • 单独的 0 合法，01、00 这样的多位前导零不合法。
  • 每段最多三位且不超过 255，越界前停止扩展，回溯后删除最后一段。

相似题目

题目 难度 关联与区别
468. 验证IP地址 中等 原题验证一个IP地址，本题枚举分段后也必须检查每段范围与前导零。
131. 分割回文串 中等 同样按子串分段回溯，原题每段需回文，本题必须四段且每段满足IPv4规则。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/43307994
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！