描述
给一个不包含0和1的数字字符串,每个数字代表一个字母,请返回其所有可能的字母组合。
下图的手机按键图,就表示了每个数字可以代表的字母。
td {white-space:pre-wrap;border:1px solid #dee0e3;}12ABC3DEF4GHI5JKL6MNO7PQRS8TUV9WXYZ
以上的答案是按照词典编撰顺序进行输出的,不过,在做本题时,你也可以任意选择你喜欢的输出顺序。
在线评测地址:领扣题库官网
样例 1:
输入: "23"
输出: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
解释:
'2' 可以是 'a', 'b' 或 'c'
'3' 可以是 'd', 'e' 或 'f'
样例 2:
输入: "5"
输出: ["j", "k", "l"]
解题思路
使用深度优先搜索算法。
源代码
KEYBOARD = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
class Solution:
@param digits: A digital string
@return: all posible letter combinations
"""
def letterCombinations(self, digits):
if not digits:
return []
results = []
self.dfs(digits, 0, [], results)
return results
def dfs(self, digits, index, chars, results):
if index == len(digits):
results.append(''.join(chars))
return
for letter in KEYBOARD[digits[index]]:
chars.append(letter)
self.dfs(digits, index + 1, chars, results)
chars.pop()
更多题解参考:九章官网solution