首页 > 代码库 > LeetCode——Restore IP Addresses

LeetCode——Restore IP Addresses

2024-07-24 05:35:34   216人阅读

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)

题目是给一个string，划分合理的ip的地址并给出包含所有合理的ip地址的list，我们知道ip地址的组成是4个部分，合理的范围是0.0.0.0~255.255.255.255。

代码主要有两个函数：

　　isValid——验证是否合理，如果开头是0则这个串必须是0，否则必须大于0小于255；

　　dfs——使用深搜的方式，搜索所有可能的组合；

所以用DFS的方式，搜索所有可能的组合，每一次搜索至第四个部分的时候，如果也是valid的话，那么这是一个合理的IP，添加到结果列表里

注意一下生成IP的细节， 添加 . 什么的。

Python代码如下：

 1 class RestoreIPAddress: 2  3     def isValid(self, src): 4         if src[0] == ‘0‘: 5             return src =http://www.mamicode.com/= ‘0‘ 6         return 255 >= int(src) > 0 7  8     def dfs(self, src, temp, res, count): 9         if count == 3 and self.isValid(src):10             res.append(temp + src)11             return12         for i in range(1, min(4, len(src))):13             sub = src[0:i]14             if self.isValid(sub):15                 self.dfs(src[i:], temp + sub + ‘.‘, res, count + 1)16 17     def restoreIpAddresses(self, s):18         if len(s) < 4 or len(s) > 12:19             return []20         res = []21         self.dfs(s, "", res, 0)22         # print(res)23         return res24 25 p = RestoreIPAddress()26 p.restoreIpAddresses("0000")

 

LeetCode——Restore IP Addresses


联系
我们