17. 电话号码的字母组合
给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
思路
- 循环出所有排列组合即可, 难点在于如何更简洁的实现出算法
- 可以循环也可以用递归, 此处使用递归更简洁
class Solution:
def letterCombinations(self, digits):
phone = {
'2':'abc','3':'def',
'4':'ghi','5':'jkl','6':"mno",
'7':'pqrs','8':'tuv','9':'wxyz'}
def backtrack(combination, next_digits):
# 如果没有数字了
if len(next_digits) == 0:
# 这个组合已经完成了
output.append(combination)
# 如果有数字
else:
# 遍历当前数字映射的所有字母
for letter in phone[next_digits[0]]:
# 将当前字母追加到组合中
# 并转到下一位数字继续
backtrack(combination + letter, next_digits[1:])
output = []
if digits:
backtrack("", digits)
return output
如果对你有帮助, 点个喜欢并关注我, 也可以评论, 谢谢, 我每天都会做一个题!
