恢复IP地址
之前面试问到的一个算法题，也是Lintcode上的一道题。
题：字符串如 "25525511111"，得到所有有效IP的组合，如["255.255.11.111","255.255.111.11"]。
解析：一个有效的IP分成4段，每一field的长度是1到3之间，且整数值要大于等于0，且小于256；此外，如果字段位数大于1，那么第一个值不能为0，比如02，这就是不合法的。
代码：
1、穷举法。
一个IP分成四部分，那么我们在字符串中该如何获得呢？
在一个字符串中，我们找5个点：0，i，j，k，len(string)。那[0:i],[i:j],[j:k],[k:len] 这四部分就是我们获得的ip字段，当然我们还是要对每一个进行如上的有效性判断，如果有效，才算是合法的ip。
看上面的那几个分片，间距都应该小于4。我们就用穷举的方法进行遍历。见代码：
#判断有效性
def isValid(ip_fields_tuple):
for field in ip_fields_tuple:
integer = int(field)
if integer >255 or integer < 0:
break
if len(field) > 1 and field[0] == '0':
break
if len(field) > 3:
break
else :
#如果没有break，就证明有效，直接执行else的语句。
return True
return False
def RestoreIpAddr(ip_string):
length = len(ip_string)
i = 1
addrs = []
while i < 4 and i < length-2:
j = i + 1
while j < i+4 and j < length-1:
k = j + 1
while k < j+4 and k < length:
first,second,third,fourth = ip_string[0:i],ip_string[i:j],ip_string[j:k],ip_string[k:length]
if isValid((first,second,third,fourth)):
addrs.append(".".join((first,second,third,fourth)))
k += 1
j += 1
i += 1
return addrs
现在采用其他的方法，递归调用。有点像字符串的全排列，但要比字符串全排列简单一些，不需要字符交换。
def isValidSingleField(field):
integer = int(field)
if integer >255 or integer < 0:
return False
if len(field) > 1 and field[0] == '0' or len(field)>3:
return False
return True
def RecurseRestoreIpAddr(ipstring):
addrs, temp_ip_array = [], []
find_field(ipstring,temp_ip_array,addrs,0)
return addrs
def find_field(ipstring,temp_ip_array,result,index):
if len(temp_ip_array) == 4:
if index != len(ipstring):
return
ip = ".".join(temp_ip_array)
#print ip
result.append(ip)
return
i = index
while i< index+3 and i < len(ipstring):
field = ipstring[index:i+1]
if isValidSingleField(field):
temp_ip_array.append(field)
#递归调用，有点类似字符串的全排列，但要比字符串全排列要简单，不用交换。
find_field(ipstring,temp_ip_array,result,i+1)
#删除当前层的元素
temp_ip_array.pop()
i += 1
--------EOF---------
微信分享/微信扫码阅读
微信分享/微信扫码阅读
