题解 | #数字字符串转化成IP地址#

有点难，一直在想怎么用dp解，其实根本不是用dp解的，大意了。

使用递归求解该题，递归函数传进去三个参数，第一个是s：剩余字符串，第二个是num，已经有的ip数字的数量，第三个是ip，目前已经组成好前面部分的ip，如255.255.255。然后如果构成完整的ip了，就存在self.result = []里就行了。

递归思路是我先取出第一个数字，第一个数字有多种可能，1位，两位，3位都有可能，然后取出第一个位的数字后，递归是找第二位数字，依次类推，如果能找到第4位数字，则是一个成功的ip，存起来就行了。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return string字符串一维数组
#
class Solution:
    def restoreIpAddresses(self , s: str):
        # write code here
        self.result = []  # 存储结果
        self.getip(s , 0 , '')
        return self.result

    def getip(self, s , num , ip):
        if len(s) == 0:
            return 
        if num == 3:
            if int(s)>=0 and int(s)<=255 and str(int(s)) == s:
                self.result.append(ip+'.'+s)
            else:
                pass
        else:
            i = 1
            while i <= len(s) and i <= 3:
                tmp = s[:i]
                if int(tmp) >= 0 and int(tmp) <= 255 and str(int(tmp)) == tmp:
                    if num == 0:
                        self.getip(s[i:],num+1,tmp)
                    else:
                        self.getip(s[i:],num+1,ip+'.'+tmp)
                i+=1


s = "0000"
print(Solution().restoreIpAddresses(s))