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
这个效果还是不错的