LeetCode|LeetCode 电话号码的字母组合 LeetCode电话号码的字母组合

电话号码的字母组合题目来源：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

文章图片
图源来自于 LeetCode 【LeetCode|LeetCode 电话号码的字母组合】示例:

输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
解题思路

回溯（全排列组合，本题不涉及到剪枝）；
列出手机号码对应的所有字母；
创建回溯函数 back_trace(combination, next_digits)，combination 表示已组合的字母，以及下一步输入的数字 next_digits；
若是没有更多的数字，根据限定条件，将已经组合完成的字母放到结果列表中；
若还有数字，则遍历后续数字所映射的字母，将字母组合。
当递归结束，返回结果列表。
时间复杂度：，其中 N 表示数字对应 3 个字母的数量，M 表示数字对应 4 个字母的数量。代表输入数字的长度。
空间复杂度：。保存的结果有个。

图解

文章图片
图解代码实现

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'] }# 回溯 def back_trace(combination, next_digits): # 限定条件 # 确定组合 if len(next_digits) == 0: res.append(combination) else: # 遍历匹配数字的字母 for elem in phone[next_digits[0]]: # 将字母组合起来 # 继续下一个字母 back_trace(combination + elem, next_digits[1:])res = [] if digits: back_trace('', digits) return res

实现结果