leetcode 17. 电话号码的字母组合

发表于 分类于 阅读次数：

解题思路

解法1

深搜，即可生成字母的数字组合

解法2

利用python3内置函数，生成笛卡尔积

代码

解法1

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
28
29
30
31
class Solution:
    def __init__(self) -> None:
        self.num_chars_mapping = {
            2: ['a', 'b', 'c'],
            3: ['d', 'e', 'f'],
            4: ['g', 'h', 'i'],
            5: ['j', 'k', 'l'],
            6: ['m', 'n', 'o'],
            7: ['p', 'q', 'r', 's'],
            8: ['t', 'u', 'v'],
            9: ['w', 'x', 'y', 'z']
        }

    def letterCombinations(self, digits: str) -> List[str]:
        return [] if not digits else self.combinate(0, digits)

    def combinate(self, index, s, combinations=[]):
        if index >= len(s):
            return combinations

        chars = self.num_chars_mapping[int(s[index])]
        if index == 0:
            combinations = chars
        else:
            tmp = []
            for combination in combinations:
                for char in chars:
                    tmp.append(combination+char)
            combinations = tmp

        return self.combinate(index+1, s, combinations)

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def __init__(self) -> None:
        self.num_chars_mapping = {
            2: ['a', 'b', 'c'],
            3: ['d', 'e', 'f'],
            4: ['g', 'h', 'i'],
            5: ['j', 'k', 'l'],
            6: ['m', 'n', 'o'],
            7: ['p', 'q', 'r', 's'],
            8: ['t', 'u', 'v'],
            9: ['w', 'x', 'y', 'z']
        }

    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        groups = [self.num_chars_mapping[int(digit)] for digit in digits]
        return [''.join(item) for item in itertools.product(*groups)]