（在说正事之前，我要推荐一个福利：你还在原价购买阿里云、腾讯云、华为云服务器吗？那太亏啦！来这里，新购、升级、续费都打折，能够为您省60%的钱呢！2核4G企业级云服务器低至69元/年，点击进去看看吧>>>)

描述
给一个不包含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

本文转自网络，原文链接：https://developer.aliyun.com/article/784588