### 描述​

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example: Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

### 代码​

#### 暴力法​

# Restore IP Addresses# 时间复杂度O(1)，空间复杂度O(1)class Solution:    def restoreIpAddresses(self, s: str) -> List[str]:        result = []        n = len(s)        for i in range(1, min(4, n-2)):            for j in range(i+1, min(i+4, n-1)):                for k in range(j+1, min(j+4, n)):                    s1, s2, s3, s4 = s[0 : i], s[i : j], s[j : k], s[k : n]                    if self.isValid(s1) and self.isValid(s2) and self.isValid(s3) and self.isValid(s4):                        result.append(s1 + "." + s2 + "." + s3 + "." + s4)        return result    @staticmethod    def isValid(s: str)->bool:        if len(s) > 3 or len(s) == 0 or (s[0] == '0' and len(s) > 1) or int(s) > 255:            return False        return True

#### DFS​

# Restore IP Addresses# 时间复杂度O(1)，空间复杂度O(1)class Solution:    def restoreIpAddresses(self, s: str) -> List[str]:        result = []        ip = [] # 存放中间结果        self.dfs(s, ip, result, 0)        return result    def dfs(self, s: str, ip: List[str], result: List[str], start: int):        '''DFS.          Args::            s: The original string            ip: Interim result            result: List of valid IP addresses            start: Current position        '''        if len(ip) == 4 and start == len(s): # 找到一个合法解            result.append(ip[0] + '.' + ip[1] + '.' + ip[2] + '.' + ip[3])            return        if len(s) - start > (4 - len(ip)) * 3: return  # 剪枝        if len(s) - start < (4 - len(ip)): return  # 剪枝        for i in range(1, 4):        #for (int i = start; i < start + 3 && i < s.length(); i++) {            if start + i > len(s): continue            num = int(s[start: start+i])            if num < 0 or num > 255: continue  # 剪枝            ip.append(s[start: start+i])            self.dfs(s, ip, result, start+i)            ip.pop()            if num == 0: break  # 不允许前缀0，但允许单个0