【LeetCode】（No.017）电话号码的字母组合
NO.17 电话号码的字母组合
一、写在前面
刷题模块的初衷是恶补数据结构和算法，不管自己的公众号怎样变化，刷题这个模块一定会保留下去，期待自己能成为offer收割机。LeetCode 第十六题传输门：【LeetCode】（No.016）最接近的三数之和今天给大家分享的是LeetCode 第十七题：电话号码的字母组合，为面试而生，期待你的加入。
二、今日题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd",
"be", "bf", "cd", "ce", "cf"].说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
三、 分析
题目大意就是输入两个数，用两个数对应的字母进行拼接。首先建立数字和字母之间的对应关系，可以建立一个字典，以键值对的形式存放数字和字母数据，然后对数字字符串digits逐位处理进行匹配，实现对应字母组合拼接。
四、解题
第一种解题方法：
class Solution:
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
# 创建字母对应的字符列表的字典
dic = {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'],
}
# 存储结果的数组
ret_str = []
if len(digits) == 0: return []
# 递归出口，当递归到最后一个数的时候result拿到结果进行for循环遍历
if len(digits) == 1:
return dic[int(digits[0])]
# 递归调用
result = self.letterCombinations(digits[1:])
# result是一个数组列表，遍历后字符串操作，加入列表
for r in result:
for j in dic[int(digits[0])]:
ret_str.append(j + r)
return ret_str
if __name__ == '__main__':
s = Solution()
print(s.letterCombinations('23'))这个题目做的人不是很多，用递归竟然还能战胜89%
第二种解题方法：
class Solution:
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits:
return []
digit2chars = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
res = [ i for i in digit2chars[digits[0]] ]
for i in digits[1:]:
res = [ m+n for m in res for n in digit2chars[i] ]
print (res)
return res 
这个效果还是不错的
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-11-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录