Q17|Q17 - Medium - 电话号码的字母组合 Q17-Medium-电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

文章图片
image 示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
循环排列组合 44 ms

class Solution: def letterCombinations(self, digits): """ :type digits: str :rtype: List[str] """ if not digits: return [] d = {"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"]} stack = d[digits[0]] for digit in digits[1:]: alpha_list = d[digit] new_stack = [] for s in stack: for a in alpha_list: new_stack.append(s+a) stack = new_stack return stack

【Q17|Q17 - Medium - 电话号码的字母组合】回溯 48 ms

class Solution: def letterCombinations(self, digits): """ :type digits: str :rtype: List[str] """ nums = ["", "", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"] res = [] if not digits: return res self.back_track(digits, nums, res, "", 0) return resdef back_track(self, digits, nums, res, temp, index): if index >= len(digits): res.append(temp) else: keyboard_nums = nums[int(digits[index])] for num in keyboard_nums: self.back_track(digits, nums, res, temp+num, index+1)