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 += k
                    tmpList.append(j)
            newList = tmpList[:]       
        return newList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三、其他人的题解

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

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23