leetcode 93 复原IP地址
z
 2019-07-04 21:28:35  

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

1
2
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        
        def dfs(ans, t, level, s):
            if level < 4 and not s:
                return 
            if level > 4 and s:
                return 
            if level == 4 and not s:
                ans.add('.'.join(t))
                return 
            for i in range(1, 4):
                temp = s[:i]
                if temp and int(temp) <= 255:
                    if len(temp) >= 2 and temp[0] == '0':
                        continue
                    t.append(temp)
                    dfs(ans, t, level+1, s[i:])
                    t.pop()

        ans = set()
        dfs(ans, [], 0, s)
        return ans