BM74　数字字符串转化成IP地址¶

中等通过率 35.53%python3核心代码模式样例通过牛客 AC字符串

牛客原题　源码

讲解章节：字符串处理

一句话

回溯切四刀，每段 1~3 位、值在 [0,255] 且无前导零。

解题思路¶

这题考什么¶

带约束的枚举，用回溯（DFS 搜索 + 撤销现场）实现，见 DFS 深度优先搜索。把字符串切成四段，等价于在串中间插三个分隔点，逐段决定「这一段取几位」。

状态：dfs(start) 表示 parts 里已经切好若干段、下一段从下标 start 开始。

- len(parts) == 4：只有 start == len(s)（字符正好用完）才算一条合法答案；
  剩下字符没用完就是把 IP 截断了，必须丢弃。
- 否则依次尝试当前段取 1、2、3 位。

一段合法要同时满足三条：

1. 不越界，且剩下的字符数喂得饱、也装得下后面的段：
   后面还有 k 段时，剩余长度必须落在 [k, 3k] 内；
2. 数值不超过 255；
3. 无前导零：长度大于 1 时首位不能是 '0'（"0" 合法，"00" 与 "01" 非法）。

第 3 条是本题最容易漏的，示例 "000256" 的答案为空正是因为它。

数据规模与复杂度¶

0 <= n <= 12，时限 2 秒（其他语言）。每段最多 3 种取法、共 4 段，搜索树的分支上界只有 3^4 = 81，再叠加剩余长度剪枝，实际访问的结点还要少得多。时间与空间都是 O(1) 量级（不计返回值），题面给的 O(n!) 只是宽松上界。

坑在哪¶

前导零。"01" 不是合法的 IP 段，但 int("01") == 1 会让只判数值的写法放行。必须在转换成整数之前先看首字符。
切完四段还必须正好用完所有字符。少判 start == n 会把 "25525522135" 的前四段合法但尾巴没切完的方案也收进答案。
三处提前退出的理由各不相同，不能互换：
前导零处用 break：本段首字符已经是 '0'，取更多位只会更非法；
数值超 255 处用 break：段越长数值只增不减，后面必然也超；
剩余长度不合适处用 continue：left 随本段变长而变小，「剩太多」的情形要靠取更长的本段来补救，break 会把可行解剪掉。
长度上下界 4 <= n <= 12 先挡一次：四段每段 1~3 位，别的长度必然无解。
parts 是共享的可变列表，递归返回后必须 pop 撤销现场，否则段会越堆越多。
判题按返回列表原样比对，顺序不能乱。这里「每段由短到长」的枚举顺序天然产出与样例一致的排列（先 "255.255.22.135" 后 "255.255.221.35"），不必额外排序；题面另注顺序无关。

样例复核¶

"1111"：每段都只能取 1 位（取 2 位会让剩余长度装不下后面的段），唯一答案 ["1.1.1.1"]，与期望输出一致。

参考实现¶

solutions/nowcoder/BM74/sol.py
from typing import List, Optional


class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        n = len(s)
        # 四段每段 1~3 位，总长必落在 [4, 12] 内，其余长度直接无解
        if n < 4 or n > 12:
            return []

        res: List[str] = []
        parts: List[str] = []           # 当前已经切好的段，回溯时要原样还原

        def dfs(start: int) -> None:
            if len(parts) == 4:
                # 四段齐了还要求字符正好用完，否则是把 IP 截断了，不算答案
                if start == n:
                    res.append(".".join(parts))
                return

            rest_seg = 4 - len(parts) - 1          # 本段之后还剩几段要切
            for length in (1, 2, 3):
                end = start + length
                if end > n:
                    break
                left = n - end                      # 本段取完后剩下的字符数
                # 后面还有 rest_seg 段，每段 1~3 位，剩余长度必须落在 [rest_seg, 3*rest_seg] 内。
                # 这里只能 continue：剩太多要靠本段取更长来补救，break 会把可行解剪掉
                if left < rest_seg or left > rest_seg * 3:
                    continue
                seg = s[start:end]
                if length > 1 and seg[0] == "0":
                    break                           # 首位是 '0' 却取了多位，取更长只会更非法
                if int(seg) > 255:
                    break                           # 段越长数值只增不减，后面必然也超 255
                parts.append(seg)
                dfs(end)
                parts.pop()                         # 撤销现场，让同一层的下一种长度从干净状态开始

        dfs(0)
        return res

BM74 数字字符串转化成IP地址¶