|
有效 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 中的任何数字。你可以按 任何 顺序返回答案。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
例：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
解析：
从整个字符串中分出一个整数，整数从一位到三位都判断一边，整数符合要求则将剩下的字符串继续同样的操作，当分出四个满足条件的整数后，再做整体判断，如果剩余字符串为0，也就是全部都分好了，那么就将结果存入即可。
class Solution(object):
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
res = [] # 结果存储
def backtrack(s, tmp):
if len(s) == 0 and len(tmp) == 4: # 终止条件
res.append('.'.join(tmp)) # 将IP地址用'.'装载好
return
if len(tmp) < 4: # 没装满四个整数
for i in range(min(3, len(s))): # 每个数最大为三位数
p, n = s[:i+1], s[i+1:] # 分出一个整数和剩下的字符串
if p and 0 <= int(p) <= 255 and str(int(p)) == p: # 判断分出的整数
backtrack(n, tmp + [p]) # 判断剩下的字符串
backtrack(s, []) # 函数运行
return res
|