Restore IP Addresses

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