17. 电话号码的字母组合
给定一个仅包含数字 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 <= 4digits[i] 是范围 ['2', '9'] 的一个数字。原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 15 MB, 提交时间: 2022-08-26 15:58:02
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return list()
phoneMap = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
groups = (phoneMap[digit] for digit in digits)
return ["".join(combination) for combination in itertools.product(*groups)]
python3 解法, 执行用时: 40 ms, 内存消耗: 15.1 MB, 提交时间: 2022-07-12 17:00:16
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
_map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
if not digits:
return []
def backtrack(index: int):
if index == len(digits):
combinations.append(''.join(combination))
else:
digit = digits[index]
for letter in _map[digit]:
combination.append(letter)
backtrack(index + 1)
combination.pop()
combinations = list()
combination = list()
backtrack(0)
return combinations