跳到主要内容

Restore IP Addresses

描述

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example: Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

分析

本质上是要将三个点.插入到字符串中,每个点有 3 个可能的位置,最多会有 27 个有效的 IP 地址,因此时间复杂度最大是 O(1),空间复杂度也是 O(1)。

可以用三层循环暴力求解,可以用深搜。

代码

暴力法

# Restore IP Addresses
# 时间复杂度O(1),空间复杂度O(1)
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
result = []
n = len(s)
for i in range(1, min(4, n-2)):
for j in range(i+1, min(i+4, n-1)):
for k in range(j+1, min(j+4, n)):
s1, s2, s3, s4 = s[0 : i], s[i : j], s[j : k], s[k : n]
if self.isValid(s1) and self.isValid(s2) and self.isValid(s3) and self.isValid(s4):
result.append(s1 + "." + s2 + "." + s3 + "." + s4)
return result

@staticmethod
def isValid(s: str)->bool:
if len(s) > 3 or len(s) == 0 or (s[0] == '0' and len(s) > 1) or int(s) > 255:
return False
return True

DFS

# Restore IP Addresses
# 时间复杂度O(1),空间复杂度O(1)
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
result = []
ip = [] # 存放中间结果
self.dfs(s, ip, result, 0)
return result

def dfs(self, s: str, ip: List[str], result: List[str], start: int):
'''DFS.
Args::
s: The original string
ip: Interim result
result: List of valid IP addresses
start: Current position
'''
if len(ip) == 4 and start == len(s): # 找到一个合法解
result.append(ip[0] + '.' + ip[1] + '.' + ip[2] + '.' + ip[3])
return

if len(s) - start > (4 - len(ip)) * 3: return # 剪枝
if len(s) - start < (4 - len(ip)): return # 剪枝

for i in range(1, 4):
#for (int i = start; i < start + 3 && i < s.length(); i++) {
if start + i > len(s): continue
num = int(s[start: start+i])

if num < 0 or num > 255: continue # 剪枝

ip.append(s[start: start+i])
self.dfs(s, ip, result, start+i)
ip.pop()

if num == 0: break # 不允许前缀0,但允许单个0