Leetcode 93. Restore IP Addresses

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Restore IP Addresses

2. Solution

解析:Version 1,容易想到的方案,枚举.所有可能的位置,然后对四个数字进行检查,如果都合法,则为合法的IP地址,也可以枚举数字。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
result = []
chars = list(s)
length = len(s)
for i in range(1, length):
for j in range(i+1, length):
for k in range(j+1, length):
num1 = ''.join(chars[:i])
num2 = ''.join(chars[i:j])
num3 = ''.join(chars[j:k])
num4 = ''.join(chars[k:])

if self.validify(num1) and self.validify(num2) and self.validify(num3) and self.validify(num4):
ip_address = num1 + '.' + num2 + '.' + num3 + '.' + num4
result.append(ip_address)
return result


def validify(self, num):
if len(num) == 0:
return False
elif len(num) > 1 and num[0] == '0':
return False
elif int(num) > 255:
return False
return True

解析:Version 2,在Version 1的基础上进行剪枝,每轮循环的遍历数量可以再减少一些,当出现数字不合理时,则进行下一次循环。

  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
result = []
chars = list(s)
length = len(s)

for i in range(1, 4):
num1 = ''.join(chars[:i])
if not self.validify(num1):
continue
for j in range(i+1, i+4):
num2 = ''.join(chars[i:j])
if not self.validify(num2):
continue
for k in range(j+1, j+4):
num3 = ''.join(chars[j:k])
num4 = ''.join(chars[k:])
if self.validify(num3) and self.validify(num4):
ip_address = num1 + '.' + num2 + '.' + num3 + '.' + num4
result.append(ip_address)
return result


def validify(self, num):
if len(num) == 0:
return False
elif len(num) > 1:
if num[0] == '0':
return False

if int(num) > 255:
return False
return True

Reference

  1. https://leetcode.com/problems/restore-ip-addresses/
如果有收获,可以请我喝杯咖啡!