-
Notifications
You must be signed in to change notification settings - Fork 1
/
0093.py
39 lines (33 loc) · 941 Bytes
/
0093.py
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
34
35
36
37
38
39
class Solution:
@cache
def deeper(self, s, have, dots):
if dots == 3:
# final part
if not s:
return
if s[0] == "0" and len(s) > 1:
return
if int(s) > 255:
return
self.result.append(have + s)
return
if not s:
return
# performance
need = 4 - dots
if need*3 < len(s):
return
# no leading zeros
if s[0] == "0":
self.deeper(s[1:], have + s[:1] + ".", dots + 1)
return
# 1,2 or 3 digits
for i in range(1, 4):
if i == 3:
if int(s[:i]) > 255:
break
self.deeper(s[i:], have + s[:i] + ".", dots + 1)
def restoreIpAddresses(self, s: str) -> List[str]:
self.result = []
self.deeper(s, "", 0)
return self.result