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:
- digits = “23”, 2 对应的是 a, b, c;3 对应的是 d, e, f。
- 将 newlist 初始化为 digits 第一个元素对应的字符,即 [“a”, “b”, “c”]。
- 循环遍历字符,从第二位开始,遇到的是 3 。
- 初始化一个空列表 tmpList 作为临时列表。
- 循环 3 对应的映射,即 [“d”, “e”, “f”],再循环 newlist ,为了把 abc 和 def 进行一一映射。将一一映射后的结果追加到 tmpList 里,最后将 tmpList 再复制给 newList,以便下一个字符再进行一一映射和追加。
- 等循环完,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
三、其他人的题解
看了下 腐烂的橘子 的题解 回溯+队列 图解,感觉还挺麻烦,之后研究下。
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
原文地址:https://blog.csdn.net/li_yizhixiaowukong/article/details/140627409
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!