Posted on 2023-01-22 02:24
Uriel 阅读(22)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
闲来无事重切Leet Code
给出一串数字，输出所有可能组成的合法的IP地址
DFS, 用list存结果
1 #93
2 #Runtime: 36 ms (Beats 47.42%)
3 #Memory: 13.5 MB (Beats 85.11%)
4
5 class Solution(object):
6 def restoreIpAddresses(self, s):
7 """
8 :type s: str
9 :rtype: List[str]
10 """
11
12 self.ans = []
13
14 def DFS(i, t):
15 if i == len(s):
16 if len(t) == 4:
17 self.ans.append('.'.join(map(str, t)))
18 return
19 if t[-1] * 10 + int(s[i]) <= 255 and t[-1]:
20 x = t[-1]
21 t[-1] = 10 * x + int(s[i])
22 DFS(i + 1, t)
23 t[-1] = x
24 if len(t) < 4:
25 t.append(int(s[i]))
26 DFS(i + 1, t)
27 t.pop()
28
29 DFS(1, [int(s[0])])
30 return self.ans