还原ip地址

题目要求

一个字符串，里面存储的是ip地址，但是.（点）被删除了，只剩下数字，请编写算法，还原这个ip地址，如果可以还原成多个，请逐一列出

输入: 192168119130
输出: ['192.168.119.130']

输入: 101224010
输出:['10.12.240.10', '10.122.40.10', '10.122.401.0', 
      '101.2.240.10', '101.22.40.10', '101.22.401.0', 
      '101.224.0.10']
      
输入: 101226010
输出: ['10.122.60.10', '101.22.60.10', '101.226.0.10']

思路分析

一个ip地址有四段，每段的范围是0~255，可以分四次从输入字符串中截取字符串，第一次截取时，必然是从字符串索引为0的位置开始，那么可以截取的长度是1， 2， 3。 这一段截取后，进行第二次截取，第二次截取的开始位置取决于第一次截取结束的位置，如果第一次截取的长度是2，那么第二次就要从索引为2的位置上开始截取，可以截取的长度是1， 2， 3， 第三次和第四次做同样的操作，这么一分析，你就应该想到用递归函数来做了。

需要考虑的情况是：

• 截取后的每一段，如果是以0开头，那么这一段只能是0，总不能出现10.21.01.23的ip地址吧，01是什么鬼

• 截取后的每一段，其值大小不能超过255

• 如果截取后剩余的部分长度超过剩余几段理论上的最大长度,那么这个截取就是不合理的，比如192168119130， 第一段只截取1，那么剩余部分92168119130 的长度是11，后面三段最长也就是9，所以这样截取是不合理的

• 如果截取后余下的部分长度是0，也是不合理的

• 如果截取后余下的部分长度比余下几段理论上的最小长度还小，也是不合理的，比如截取后余下部分长度是2，可是还有3段需要截取，这样就是不合理的

示例代码

# coding=utf-8


def restore_ip(ip):
    retsection_lst = restore_ip_ex(ip, len(ip), 0, 4)
    return ['.'.join(item) for item in retsection_lst]


def restore_ip_ex(ip, ip_len, start_index, k):
    if k == 0:
        return [[]]

    if ip_len > 20 or ip_len < 4:
        return []

    section_lst = []
    for i in range(1, 4):
        # 如果截取后剩余的部分长度超过剩余几段理论上的最大长度,那么这个截取就是不合理的
        # 如果剩余长度为0也是不合理的
        rest_len = ip_len - i - start_index
        if (rest_len == 0 and k != 1) or rest_len > (k-1)*3 or rest_len < k-1:
            continue

        section = ip[start_index:start_index+i]
        # 如果某段以0开头,那么这一段就是只能是0,否则就会出现1.012.240.10这种情况,012显然是不合理的
        if section[0] == '0' and len(section) != 1:
            continue

        if int(section) > 255:
            continue

        # 截取下一段
        res_lst = restore_ip_ex(ip, ip_len, i+start_index, k-1)
        for item in res_lst:
            item.insert(0, section)

        section_lst.extend(res_lst)

    return section_lst


if __name__ == '__main__':
    print restore_ip("192168119130")
    print restore_ip("101224010")
    print restore_ip("1111")
    print restore_ip("101226010")