0093. Restore IP Addresses ========================== 题目信息 -------- :题号: 0093. 复原 IP 地址 :难度: Medium :主题: 字符串、回溯、固定分段、长度剪枝 :原题: `LeetCode 0093 `_ :重点: 从枚举三个分隔点,推导到按段搜索并利用剩余长度提前剪枝 题目重述 -------- 给定只包含数字的字符串 ``s``,在不改变字符顺序、不删除字符的前提下插入三个点,返回所有可能的 合法 IPv4 地址。 每个地址必须恰好包含四段。每段长度为 1 到 3,数值位于 ``0..255``;单独的 ``0`` 合法,长度大于 1 的段不能以 ``0`` 开头。四段必须完整使用原字符串中的全部字符,答案顺序不限。 约束为 ``1 <= s.length <= 20``。 自建示例 -------- .. code-block:: text 输入:s = "11211" 输出:["1.1.2.11", "1.1.21.1", "1.12.1.1", "11.2.1.1"] 字符串长度为 5,因此四段中恰有一段长度为 2。四种放置方式得到的段都合法。 .. code-block:: text 输入:s = "00101" 输出:["0.0.10.1"] ``00``、``01`` 都有前导零,只有 ``0 | 0 | 10 | 1`` 合法。 .. code-block:: text 输入:s = "1234567890123" 输出:[] 四段最多容纳 12 个字符,长度为 13 时不可能构成 IPv4 地址。 C++ 实现 -------- .. code-block:: cpp #include #include #include 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& parts) { return parts[0] + "." + parts[1] + "." + parts[2] + "." + parts[3]; } std::vector enumerateLengths(const std::string& s) { std::vector result; int n = static_cast(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& parts, std::vector& result) { if (depth == 4) { if (index == static_cast(s.size())) { result.push_back(buildAddress(parts)); } return; } for (int length = 1; length <= 3 && index + length <= static_cast(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& parts, std::vector& result) { int segments_left = 4 - depth; int chars_left = static_cast(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(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 restoreIpAddresses(std::string s) { std::vector result; std::array parts; prunedDfs(s, 0, 0, parts, result); return result; } }; 题解 ---- 分隔点枚举 ~~~~~~~~~~ 地址由四段组成,任意答案都可唯一表示为四个段长 ``a,b,c,d``。每个段长只能取 1、2、3,因此先枚举 前三段长度,第四段由总长度确定: .. code-block:: text d = n - a - b - c 只有 ``1 <= d <= 3`` 时才继续验证四段。该方法直接展示了问题的有限搜索空间,但每组段长都要重复 计算起点、截取子串和验证四段。 合法段判定 ~~~~~~~~~~ 每段同时受两个条件限制。长度大于 1 且首字符为 ``0`` 时,段具有前导零;否则按十进制累积数值, 最终必须不超过 255。 .. code-block:: text value = value * 10 + digit 段长最多为 3,不需要通用整数解析,也不存在溢出风险。 回溯状态 ~~~~~~~~ ``dfs(index, depth)`` 表示前 ``index`` 个字符已经组成 ``depth`` 个合法段。下一步只需从当前位置选择 1 到 3 个字符作为新段: .. code-block:: text index -> 下一段起点 depth -> 已完成段数 parts -> 已选择的段 字符顺序固定,下一段起点由上一段终点唯一决定,因此不需要访问标记。深度达到 4 时,只有 ``index == s.size()`` 才能提交答案。 剩余长度剪枝 ~~~~~~~~~~~~ 设剩余段数为 ``segments_left``,剩余字符数为 ``chars_left``。每段至少使用 1 个字符、至多使用 3 个 字符,因此可行状态必须满足: .. code-block:: text segments_left <= chars_left <= 3 * segments_left 该条件在递归入口统一检查。字符串少于 4 位或多于 12 位时,根状态立即失败;搜索过程中字符过多或 过少的分支也会提前停止。 增量构造 ~~~~~~~~ 剪枝版本在枚举段长时同步累积数值。当前段首字符为 ``0`` 时,只允许长度 1;尝试更长段必然产生 前导零,因此直接结束本层循环。数值超过 255 后,追加更多数字只会使数值更大,同样可以结束循环。 .. code-block:: text 首字符为 0:只保留 "0" 当前值 > 255:更长候选全部非法 这样无需对每个候选重新从头扫描字符。 路径唯一性 ~~~~~~~~~~ 任意合法地址都有唯一的四段长度序列,回溯会沿该序列选择四次,因此不会遗漏。两条不同路径首次 选择不同段长时,对应的点位置已经不同,所以不会生成同一地址。每段在加入路径前已验证,深度 4 又由剩余长度条件保证没有未消费字符,因此提交的字符串一定合法。 复杂度 ~~~~~~ IPv4 固定为四段,每层最多尝试三个长度,搜索树规模至多 ``O(3^4)``,可视为常数;构造输出仍需 与答案数量成正比。递归深度和路径均固定为 4,除返回结果外额外空间为 ``O(1)``。