- 标签:深度优先搜索、递归、字符串、回溯算法
- 难度:中等
题目大意
#
给定一个只包含数字 2~9 的字符串,返回它在九宫格键盘上所能表示的所有字母组合。答案可以按 「任意顺序」返回。

解题思路
#
用哈希表保存每个数字键位对应的所有可能的字母,然后进行回溯操作。
回溯过程中,维护一个字符串 combination,表示当前的字母排列组合。初始字符串为空,每次取电话号码的一位数字,从哈希表中取出该数字所对应的所有字母,并将其中一个插入到 combination 后面,然后继续处理下一个数字,知道处理完所有数字,得到一个完整的字母排列。开始进行回退操作,遍历其余的字母排列。
代码
#
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:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
phone_dict = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
def backtrack(combination, index):
if index == len(digits):
combinations.append(combination)
else:
digit = digits[index]
for letter in phone_dict[digit]:
backtrack(combination + letter, index + 1)
combinations = list()
backtrack('', 0)
return combinations
|