[leetcode/lintcode 题解]大厂面试真题详解： 电话号码的字母组

描述
给一个不包含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
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！