问题描述：
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
问题分析：
很显然是，是回溯题目，递归求解，可以使用深度优先（dfs）的思想。
（1）用 index 记录 digits 字符串中的字符索引。
（2）用 paths 表示走过的字符，走到头，就保存到 res， 然后回溯当上一层，继续。
（3）这个过程相当于深度优先搜索。
Python3实现：
class Solution:def letterCombinations(self, digits):if not digits: return [] # 如果为空，返回空列表dict = {'1': [''],'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']}# index 表示 digits字符串中的字符索引# paths 表示走过的字符串，走到头，就保存到 res， 然后回溯当上一个位置，继续。def dfs(dict, digits, index, paths, res): # 定义内部，递归函数if index == len(digits):res.append(paths)returnfor s in dict[digits[index]]:dfs(dict, digits, index + 1, paths + s, res)res = []dfs(dict, digits, 0, '', res)return resif __name__ == '__main__':digits = '92'solu = Solution()print(solu.letterCombinations(digits))其他实现：
（1）使用Python functools 库中的 reduce 函数实现，注：经测试，这种方式最快（这三个方法）。
# @Time :2018/7/7
# @Author :LiuYinxing
from functools import reduceclass Solution:def letterCombinations(self, digits):if not digits: return [] # 如果为空，返回空列表dict = {'1': [''],'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']}return reduce(lambda acc, digit: [x + y for x in acc for y in dict[digit]], digits, [''])if __name__ == '__main__':digits = '9562'solu = Solution()print(solu.letterCombinations(digits))（2）使用Python itertools 库中的 product（求集合的笛卡尔积），注：经测试，这种方式最慢（这三个方法）。
# @Time :2018/7/7
# @Author :LiuYinxing
from itertools import productclass Solution:def letterCombinations(self, digits):if not digits: return [] # 如果为空，返回空列表dict = {'1': [''],'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']}input = [dict[digit] for digit in digits] # 获取对应的字符return [''.join(i) for i in product(*input)] # 使用 product 做笛卡尔积if __name__ == '__main__':digits = '92'solu = Solution()print(solu.letterCombinations(digits))欢迎指正哦。
本文链接：https://my.lmcjl.com/post/8243.html
展开阅读全文
4 评论