给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
- 0 <= digits.length <= 4
- digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
使用递归。
- 终止条件：遍历完所有数字，追加到 res 中。
- 递推工作：将 nextdigit 中“每一个数字和其映射的一个字母”追加到 conbination 中。
- 返回值：无。
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits: return []
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 backtrack(conbination, nextdigit):
if len(nextdigit) == 0:
res.append(conbination)
return
for letter in phone[nextdigit[0]]:
backtrack(conbination + letter, nextdigit[1:])
res = []
backtrack('', digits)
return res
当输入包含 m 个对应 3 个字母的数字和 n 个对应 4 个字母的数字时，不同的字母组合一共有 3^M*4^N 种，需要遍历每一种组合。
- 空间复杂度 *
O*(M + N)：M 是对应三个字母的数字个数，N 是对应四个字母的数字个数。 - 时间复杂度 *
O*(3^M*4^N)：M 是对应三个字母的数字个数，N 是对应四个字母的数字个数。