Leetcode 17. 电话号码的字母组合

Leetcode 17. 电话号码的字母组合

一、题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：
输入：digits = “”
输出：[]

示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

二、我的想法

例如示例 1：

1. digits = “23”， 2 对应的是 a, b, c；3 对应的是 d, e, f。
2. 将 newlist 初始化为 digits 第一个元素对应的字符，即 [“a”, “b”, “c”]。
3. 循环遍历字符，从第二位开始，遇到的是 3 。
4. 初始化一个空列表 tmpList 作为临时列表。
5. 循环 3 对应的映射，即 [“d”, “e”, “f”]，再循环 newlist ，为了把 abc 和 def 进行一一映射。将一一映射后的结果追加到 tmpList 里，最后将 tmpList 再复制给 newList，以便下一个字符再进行一一映射和追加。
6. 等循环完，newList 即为所求。

class Solution:def letterCombinations(self, digits: str) -> List[str]:digitsLen = len(digits)if digitsLen == 0:return []digitWord = {"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"]}newList = digitWord[digits[0]]for i in range(1, digitsLen):tmpList = list()for k in digitWord[digits[i]]:for j in newList:j += ktmpList.append(j)newList = tmpList[:]       return newList

三、其他人的题解

看了下 腐烂的橘子 的题解 回溯+队列 图解，感觉还挺麻烦，之后研究下。

class Solution:def letterCombinations(self, digits: str) -> List[str]:if not digits: return []phone = {'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']}def backtrack(conbination,nextdigit):if len(nextdigit) == 0:res.append(conbination)else:for letter in phone[nextdigit[0]]:backtrack(conbination + letter,nextdigit[1:])res = []backtrack('',digits)return res