93. Restore IP Addresses

class Solution:
    def isValid(self, s):
        if not s or len(s) > 3 or (len(s) > 1 and s[0] == '0'):
            return False
        else:
            res = int(s)
            return res <= 255 and res >=0

    def backtrack(self, s, k, addr, res):
        if k == 0:
            if not s:
                res.append(addr)
                return

        else:
            for i in range(1, 4):
                if len(s) > i and self.isValid(s[:i]):
                    if k == 1:
                        self.backtrack(s[i:], k-1, addr + s[:i], res)
                    else:
                        self.backtrack(s[i:], k-1, addr + s[:i] + "." , res)
        return

    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = []
        self.backtrack(s, 4, "", res)
        return res