LintCode 恢复IP地址

本文主要是介绍LintCode 恢复IP地址，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。

样例
给出字符串 “25525511135”，所有可能的IP地址为：

[
“255.255.11.135”,
“255.255.111.35”
]

和LintCode 电话号码的字母组合类似。
首先找到合适的位数组合。一共4位，每一位的长度要大于等于1，小于等于3，且4位和为字符串长度.
另外要判断每1 位的数字组合，是否合乎规则，比如不能超过255，不能0开头。

class Solution:"""@param: s: the IP string@return: All possible valid IP addresses"""def restoreIpAddresses(self, s):# write your code heren=len(s)a=""  #记录每一位的长度。此处用字符串来记录，导致后面判断时类型转换很繁琐。但是直接用list来存数字，在递归的时候数据传递有点问题，是我对python的不太理解导致，这个问题有待解决。result=[]self.work(n,a,result,s)return resultdef work(self,n,a,result,s):if len(a)==3:num4=n-int(a[0])-int(a[1])-int(a[2])if num4<=3 and num4>=1 :a+=str(num4)print atemp=self.judge(a,n,s)if temp!='#':result.append(temp)a=a[:-1]return for x in range(1,4):a+=str(x)self.work(n,a,result,s)a=a[:-1]def judge(self,a,n,s):if int(s[:int(a[0])])>255 or int(s[int(a[0]):int(a[0])+int(a[1])])>255 or\int(s[int(a[0])+int(a[1]):int(a[0])+int(a[1])+int(a[2])])>255 or int(s[int(a[0])+int(a[1])+int(a[2]):])>255:return '#'elif (s[:int(a[0])][0]=='0' and a[0]!='1') or\(s[int(a[0]):int(a[0])+int(a[1])][0]=='0' and a[1]!='1') or\(s[int(a[0])+int(a[1]):int(a[0])+int(a[1])+int(a[2])][0]=='0' and a[2]!='1') or\(s[int(a[0])+int(a[1])+int(a[2]):][0]=='0' and a[3]!='1'):return '#'else:return s[:int(a[0])]+'.'+s[int(a[0]):int(a[0])+int(a[1])]+'.'+\s[int(a[0])+int(a[1]):int(a[0])+int(a[1])+int(a[2])]+'.'+s[int(a[0])+int(a[1])+int(a[2]):]

上面代码中那个注释的问题，解决了，原因就是list的问题。在work函数中，对存储数字的list进行操作时，复制一个新的list就行了。代码如下：

class Solution:"""@param: s: the IP string@return: All possible valid IP addresses"""def restoreIpAddresses(self, s):# write your code heren=len(s)a=[]result=[]self.work(n,a,result,s)return resultdef work(self,n,b,result,s):a=list(b)  #相当于又构建了一个列表，这样对其修改就不会影响原来的列表。注意直接a=b是不行的，可以利用id（a），id（b）实际观察一下，很清楚。if len(a)==3:num4=n-a[0]-a[1]-a[2]if num4<=3 and num4>=1 :a.append(num4)print atemp=self.judge(a,n,s)if temp!='#':result.append(temp)a=a[:-1]return for x in range(1,4):a.append(x)self.work(n,a,result,s)a=a[:-1]def judge(self,a,n,s):if int(s[:a[0]])>255 or int(s[a[0]:a[0]+a[1]])>255 or\int(s[a[0]+a[1]:a[0]+a[1]+a[2]])>255 or int(s[a[0]+a[1]+a[2]:])>255:return '#'elif (s[:a[0]][0]=='0' and a[0]!=1) or\(s[a[0]:a[0]+a[1]][0]=='0' and a[1]!=1) or\(s[a[0]+a[1]:a[0]+a[1]+a[2]][0]=='0' and a[2]!=1) or\(s[a[0]+a[1]+a[2]:][0]=='0' and a[3]!=1):return '#'else:return s[:a[0]]+'.'+s[a[0]:a[0]+a[1]]+'.'+\s[a[0]+a[1]:a[0]+a[1]+a[2]]+'.'+s[a[0]+a[1]+a[2]:]

这篇关于LintCode 恢复IP地址的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---