电话号码的字母组合

发表于 分类于 阅读次数：

电话号码的字母组合（难度：中等）

1

方法：回溯

2
img
代码
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
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone = {'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']}

        output = []
        if digits:
            self.backtrack("", digits, phone, output)
        return output

    def backtrack(self, combination, digit, phone, output):
        if len(digit)==0:
            output.append(combination)
            return
        
        for letter in phone[digit[0]]:
            self.backtrack(combination+letter,digit[1:], phone, output)

4
3