https://leetcode.com/problems/restore-ip-addresses/description/
首先复习一下关于IP地址部分的知识
ip地址是一个32位二进制数，通常被分为4个小节，8位一个小节，用对应10进制来表示，'.'字符隔开。
遇到字符串的子序列或配准问题首先想到的是动态规划，只要遇到需要求出列出所有可能情况的首先用递归。这一题是需要列出所有可能的解，更符合第二种情况。
class Solution(object):
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
k = 4
out =""
res = []
self.restore(s,k,out,res)
return res
def restore(self, s, k ,out, res):
if k == 0 and len(s) == 0 and out not in res:
res.append(out)
return
else:
for size in range(1,4):
t = s[:size]
if len(t) <= len(s) and self.valid(s[:size]) == 1:
if k == 1:
self.restore(s[size:], k - 1, out + t, res)
else:
self.restore(s[size:], k - 1, out + t +'.', res)
def valid(self,s):
if int(s) > 256 or int(s) < 0:
return 0
elif len(s) > 1 and s[0] == '0':
return 0
elif len(s) == 0:
return 0
else:
return 1
