93. Restore IP Addresses

class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        return self.recursion(s,3,'',[])
        
    def recursion(self,s,k,cur,res):
        if k==0 :
            if self.isValid(s):
                cur+=s
                res.append(cur)
                return res
            else: return 
        
        for i in xrange(1,4):
            if i>(len(s)-k):continue
            if self.isValid(s[:i]):
                cur+=(s[:i]+'.')
                self.recursion(s[i:],k-1,cur,res)
                cur=cur[:-i-1]
        return res
        
    def isValid(self,s):
        return int(s)<=255 and str(int(s))==s