给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

    有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

    例如：”0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1” 是 无效的 IP 地址。

    示例 1：

    输入：s = “25525511135”
    输出：[“255.255.11.135”,”255.255.111.35”]
    示例 2：

    输入：s = “0000”
    输出：[“0.0.0.0”]
    示例 3：

    输入：s = “1111”
    输出：[“1.1.1.1”]
    示例 4：

    输入：s = “010010”
    输出：[“0.10.0.10”,”0.100.1.0”]
    示例 5：

    输入：s = “101023”
    输出：[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]

    提示：

    0 <= s.length <= 3000
    s 仅由数字组成

    解法一：DFS
    利用DFS思想在字符串上完成搜索。从字符串起始位置开始，先找到所有0～255范围内的后续串，每一个串构成当前IP段，然后对剩余段做相同操作。共需执行至深度为4或者字符串已经消耗完。

    注意构造IP段时的特殊情况，即IP段起始为0时，该段只能为0。

    1. class Solution:
    2.     def restoreIpAddresses(self, s: str) -> List[str]:
    3.         ans, segs = [], [0, 0, 0, 0]
    5.         def dfs(start, depth):
    6.             # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
    7.             if depth == 4:
    8.                 if start == len(s):
    9.                     ans.append(".".join(str(seg) for seg in segs))
    10.                 return
    12.             # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
    13.             if start == len(s):
    14.                 return
    16.             # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
    17.             if s[start] == "0":
    18.                 segs[depth] = 0
    19.                 dfs(start + 1, depth + 1)
    21.             # 一般情况，枚举每一种可能性并递归
    22.             seg = 0
    23.             for i in range(start, len(s)):
    24.                 seg = seg * 10 + (ord(s[i]) - ord("0"))
    25.                 if 0 < seg <= 255:
    26.                     segs[depth] = seg
    27.                     dfs(i + 1, depth + 1)
    28.                 else:
    29.                     break
    31.         dfs(0, 0)
    32.         return ans

    函数签名改为dfs(s)，这时segs需要回溯，避免状态污染后面的查找。

    1. class Solution:
    2.     def restoreIpAddresses(self, s: str) -> List[str]:
    3.         ans = []
    4.         segs = []
    6.         def dfs(s):
    7.             # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
    8.             if len(segs) == 4:
    9.                 if not s:
    10.                     ans.append(".".join(str(seg) for seg in segs))
    11.                 return
    13.             # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
    14.             if not s:
    15.                 return
    17.             # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
    18.             if s[0] == "0":
    19.                 segs.append(0)
    20.                 dfs(s[1:])
    21.                 segs.pop()
    23.             # 一般情况，枚举每一种可能性并递归
    24.             seg = 0
    25.             for i, c in enumerate(s):
    26.                 seg = seg * 10 + (ord(c) - ord("0"))
    27.                 if 0 < seg <= 255:
    28.                     segs.append(seg)
    29.                     dfs(s[i+1:])
    30.                     segs.pop()
    31.                 else:
    32.                     return
    34.         dfs(s)
    35.         return ans