Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一串数字,输出所有可能组成的合法的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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理