LeetCode 93.复原IP地址 Python题解
# 复原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地址。
给定一个只包含数字的字符串s，用以表示一个IP地址，返回所有可能的有效IP地址，
这些地址可以通过在s中插入'.'来形成。你不能重新排序或删除s中的任何数字。你可以按任何顺序返回答案。
"""
class Solution:
def restoreIpAddresses(self, s):
du = 4
ans = list()
segments = [0] * du
def dfs(pointer, step):
# 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
if pointer == du:
if step == len(s):
ipAddr = ".".join(str(seg) for seg in segments)
ans.append(ipAddr)
return
# 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提退出
if step == len(s):
return
# 0记录跳过
if s[step] == "0":
segments[pointer] = 0
dfs(pointer + 1, step + 1)
return
# 一般情况，枚举每一种可能性并递归
addr = 0
for segEnd in range(step, len(s)):
addr = addr * 10 + (ord(s[segEnd]) - ord("0"))
if 0 < addr <= 0xFF:
segments[pointer] = addr
dfs(pointer + 1, segEnd + 1)
else:
break
dfs(0, 0)
return ans
s = "25525511135"
a = Solution()
print(a.restoreIpAddresses(s))
# 其实这道题还是很简单的，但是有一个思考空间就是说字符串S怎么循环查找
# 这个是需要思考的，其实也还好，因为其实是循环问题思考一下就可以
# 就是普通的递归与回溯了