题目

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.'分隔。

示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

方案（回溯）

  1. class Solution:
  2.     def restoreIpAddresses(self, s: str) -> List[str]:
  3.         if len(s) <= 3:
  4.             return []
  6.         # 回溯
  7.         # 我们现在有4个 . 每个数字后可以选择放或者不放，然后放完之后判断是否合法即可
  8.         # 注: "0.0.0.0" 合法, 但是 "0.00.1.0" 不合法
  9.         ret = []
  11.         def helper(index, count, prefix):
  12.             '''
  13.             index: 当前处理到 s 的 index
  14.             count: 已放置 . 的个数
  15.             prefix: 已经放置的结果, eg. prefix = "255.255.11."
  16.             '''
  17.             if index >= len(s):
  18.                 return
  20.             if count == 3:
  21.                 if s[index] == "0" and len(s) - index > 1: # 结尾为 0x, 0xx
  22.                     return
  23.                 if int(s[index:]) > 255:
  24.                     return
  25.                 ret.append(prefix + s[index:])
  27.             count += 1
  29.             if s[index] == "0":
  30.                 return helper(index+1, count, prefix+s[index:index+1]+".")
  32.             if len(s) - index >= 1:
  33.                 helper(index+1, count, prefix+s[index:index+1]+".")
  34.             if len(s) - index >= 2:
  35.                 helper(index+2, count, prefix+s[index:index+2]+".")
  36.             if len(s) - index >= 3 and int(s[index:index+3]) <= 255:
  37.                 helper(index+3, count, prefix+s[index:index+3]+".")
  39.         helper(0, 0, "")
  40.         return ret

原文

https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/292/simulation/1309/