【LeetCode】17. 电话号码的字母组合

1 问题

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

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

示例 1：

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

示例 2：

输入：digits = “”
输出：[]

示例 3：

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

2 答案

自己写的不对

class Solution:def letterCombinations(self, digits: str) -> List[str]:hashmap = {2:'abc', 3:'def', 4:'ghi', 5:'jkl', 6:'mno', 7:'pqrs', 8:'tuv', 9:'wxyz'}if digits = "" return []list1 = []res = []for s in digits:list1.append(hashmap[int(s)])for i in range(len(list1)):for j in range(i+1, len(list1)):ii = len(list1[i])jj = len(list1[j])while ii != -1: res.append(list1[i][ii]+list1[j][jj])ii -= 1

官方解1：回溯

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

官方解2：队列

class Solution:def letterCombinations(self, digits: str) -> List[str]:if not digits: return []phone = ['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']queue = ['']  for digit in digits:for _ in range(len(queue)):tmp = queue.pop(0)for letter in phone[ord(digit)-50]:queue.append(tmp + letter)return queue

感觉这两种方法都不太好理解，后面还要巩固一下

3 知识点

回溯：
当题目中出现 “所有组合” 等类似字眼时，我们第一感觉就要想到用回溯。