题目
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
思路
深度优先遍历的思想
实现
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
segments = [0] * 4
result = []
def dfs(id, idx):
if id == 4:
if idx == len(s):
ipAddr = ".".join(str(seg) for seg in segments)
result.append(ipAddr)
return if idx == len(s):
return if s[idx] == "":
segments[id] = 0
dfs(id + 1, idx + 1) addr = 0
for j in range(idx, len(s)):
addr = addr * 10 + (ord(s[j]) - ord(""))
if 0 < addr <= 0xFF:
segments[id] = addr
dfs(id + 1, j + 1)
else:
break
dfs(0,0)
return result