0093. Restore IP Addresses

题目信息

题号:
  1. 复原 IP 地址

难度:

Medium

主题:

字符串、回溯、固定分段、长度剪枝

原题:

LeetCode 0093

重点:

从枚举三个分隔点,推导到按段搜索并利用剩余长度提前剪枝

题目重述

给定只包含数字的字符串 s,在不改变字符顺序、不删除字符的前提下插入三个点,返回所有可能的 合法 IPv4 地址。

每个地址必须恰好包含四段。每段长度为 1 到 3,数值位于 0..255;单独的 0 合法,长度大于 1 的段不能以 0 开头。四段必须完整使用原字符串中的全部字符,答案顺序不限。

约束为 1 <= s.length <= 20。

自建示例

输入:s = "11211"
输出:["1.1.2.11", "1.1.21.1", "1.12.1.1", "11.2.1.1"]

字符串长度为 5,因此四段中恰有一段长度为 2。四种放置方式得到的段都合法。

输入:s = "00101"
输出:["0.0.10.1"]

00、01 都有前导零,只有 0 | 0 | 10 | 1 合法。

输入:s = "1234567890123"
输出:[]

四段最多容纳 12 个字符,长度为 13 时不可能构成 IPv4 地址。

C++ 实现

#include <array>
#include <string>
#include <vector>

class Solution {
private:
    bool validSegment(const std::string& s, int start, int length) {
        if (length > 1 && s[start] == '0') {
            return false;
        }

        int value = 0;
        for (int offset = 0; offset < length; ++offset) {
            value = value * 10 + s[start + offset] - '0';
        }
        return value <= 255;
    }

    std::string buildAddress(const std::array<std::string, 4>& parts) {
        return parts[0] + "." + parts[1] + "." + parts[2] + "." + parts[3];
    }

    std::vector<std::string> enumerateLengths(const std::string& s) {
        std::vector<std::string> result;
        int n = static_cast<int>(s.size());

        for (int first = 1; first <= 3; ++first) {
            for (int second = 1; second <= 3; ++second) {
                for (int third = 1; third <= 3; ++third) {
                    int fourth = n - first - second - third;
                    if (fourth < 1 || fourth > 3) {
                        continue;
                    }

                    int second_start = first;
                    int third_start = first + second;
                    int fourth_start = first + second + third;

                    if (!validSegment(s, 0, first) ||
                        !validSegment(s, second_start, second) ||
                        !validSegment(s, third_start, third) ||
                        !validSegment(s, fourth_start, fourth)) {
                        continue;
                    }

                    result.push_back(
                        s.substr(0, first) + "." +
                        s.substr(second_start, second) + "." +
                        s.substr(third_start, third) + "." +
                        s.substr(fourth_start, fourth));
                }
            }
        }
        return result;
    }

    void basicDfs(const std::string& s, int index, int depth,
                  std::array<std::string, 4>& parts,
                  std::vector<std::string>& result) {
        if (depth == 4) {
            if (index == static_cast<int>(s.size())) {
                result.push_back(buildAddress(parts));
            }
            return;
        }

        for (int length = 1;
             length <= 3 && index + length <= static_cast<int>(s.size());
             ++length) {
            if (!validSegment(s, index, length)) {
                continue;
            }

            parts[depth] = s.substr(index, length);
            basicDfs(s, index + length, depth + 1, parts, result);
        }
    }

    void prunedDfs(const std::string& s, int index, int depth,
                   std::array<std::string, 4>& parts,
                   std::vector<std::string>& result) {
        int segments_left = 4 - depth;
        int chars_left = static_cast<int>(s.size()) - index;

        if (chars_left < segments_left || chars_left > 3 * segments_left) {
            return;
        }
        if (depth == 4) {
            result.push_back(buildAddress(parts));
            return;
        }

        int value = 0;
        for (int length = 1;
             length <= 3 && index + length <= static_cast<int>(s.size());
             ++length) {
            if (length > 1 && s[index] == '0') {
                break;
            }

            value = value * 10 + s[index + length - 1] - '0';
            if (value > 255) {
                break;
            }

            parts[depth] = s.substr(index, length);
            prunedDfs(s, index + length, depth + 1, parts, result);
        }
    }

public:
    std::vector<std::string> restoreIpAddresses(std::string s) {
        std::vector<std::string> result;
        std::array<std::string, 4> parts;
        prunedDfs(s, 0, 0, parts, result);
        return result;
    }
};

题解

分隔点枚举

地址由四段组成,任意答案都可唯一表示为四个段长 a,b,c,d。每个段长只能取 1、2、3,因此先枚举 前三段长度,第四段由总长度确定:

d = n - a - b - c

只有 1 <= d <= 3 时才继续验证四段。该方法直接展示了问题的有限搜索空间,但每组段长都要重复 计算起点、截取子串和验证四段。

合法段判定

每段同时受两个条件限制。长度大于 1 且首字符为 0 时,段具有前导零;否则按十进制累积数值, 最终必须不超过 255。

value = value * 10 + digit

段长最多为 3,不需要通用整数解析,也不存在溢出风险。

回溯状态

dfs(index, depth) 表示前 index 个字符已经组成 depth 个合法段。下一步只需从当前位置选择 1 到 3 个字符作为新段:

index  -> 下一段起点
depth  -> 已完成段数
parts  -> 已选择的段

字符顺序固定,下一段起点由上一段终点唯一决定,因此不需要访问标记。深度达到 4 时,只有 index == s.size() 才能提交答案。

剩余长度剪枝

设剩余段数为 segments_left,剩余字符数为 chars_left。每段至少使用 1 个字符、至多使用 3 个 字符,因此可行状态必须满足:

segments_left <= chars_left <= 3 * segments_left

该条件在递归入口统一检查。字符串少于 4 位或多于 12 位时,根状态立即失败;搜索过程中字符过多或 过少的分支也会提前停止。

增量构造

剪枝版本在枚举段长时同步累积数值。当前段首字符为 0 时,只允许长度 1;尝试更长段必然产生 前导零,因此直接结束本层循环。数值超过 255 后,追加更多数字只会使数值更大,同样可以结束循环。

首字符为 0:只保留 "0"
当前值 > 255:更长候选全部非法

这样无需对每个候选重新从头扫描字符。

路径唯一性

任意合法地址都有唯一的四段长度序列,回溯会沿该序列选择四次,因此不会遗漏。两条不同路径首次 选择不同段长时,对应的点位置已经不同,所以不会生成同一地址。每段在加入路径前已验证,深度 4 又由剩余长度条件保证没有未消费字符,因此提交的字符串一定合法。

复杂度

IPv4 固定为四段,每层最多尝试三个长度,搜索树规模至多 O(3^4),可视为常数;构造输出仍需 与答案数量成正比。递归深度和路径均固定为 4,除返回结果外额外空间为 O(1)。