#!/usr/bin/env python3

__author__ = 'Wei Mu'

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        if len(s) < 4 or len(s) > 12 or s == "":
            return []
        
        return self.helper_func(s, level = 3)
    
    def helper_func(self, s, level):

        if level == 0 and int(s) <= 255:
            return [s]
        elif level == 0:
            return None
        
        ans = []
        
        for i in range(1,4):
            ip_return = None
            
            temp = s[0:i]
            
            if (len(temp) > 1 and temp[0] == '0') or (len(s[i:]) > 1 and s[i] == '0' and level == 1):
                continue
            
            if int(temp) <= 255 and i < len(s):
                ip_return = self.helper_func(s[i:], level - 1)
            
            if ip_return != None:
                for j in ip_return:
                    if j != None:
                        ans.append(temp + '.' + j)

        return ans
