93. Restore IP Addresses

找出一个由纯数字组成的序列能够构成的不同的IP地址

思路： dfs, IP地址由四部分，每部分由1到3位的数字组成，每个数字小于等于255

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        # 6 star, dfs
        rs = []
        self.dfs(s, 0, rs, [])
        return rs

    def dfs(self, s, parts, rs, path):
        if parts == 4:
            if s == "":
                rs.append(".".join(path))
            else:
                return
        for i in range(1, 4):
            if i <= len(s) and int(s[:i]) <= 255:
                if i > 1 and s[0] == "0":  # 除了0以外不能有03这种以0开头的
                    break
                self.dfs(s[i:], parts+1, rs, path+[s[:i]])