LeetCode 刷题小本本Day9 Letter Combinations of a Phone Number （回溯）

题目

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

我的答案：

1. 读懂题目之后，感觉挺简单的呀，不就是两两组合吗，可是后来仔细一想，如果一下子输入8个数字，岂不是要循环8次啊。
2. 写的时候发现一个问题：我一开始并不知道需要循环多少次呀，不能直接写for循环呀。
3. 想到的笨办法：建立一个字典存储每个数字的value；设置8次循环，如果数字没有出现在digits中就把字典的value设为空。
4. 忘记了输入重复字符了！哎呀。那这样的话，就不能确定循环次数了，啊啊啊，又不会了。还是看看答案吧。原来要用到回溯法。 啊啊，都不知道什么是回溯，(╥╯^╰╥)

回溯法：

1. 思想就是走不通就往回走；出现“所有组合”，应该考虑回溯法。
2. ”回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。
3. 排列组合、树形结构，问题转化成了从根节点到空节点一共有多少条路径。
   
   这里用到了递归嘛，不过我还是搞不太明白递归要怎么写(ಥ﹏ಥ)
   看了一下解析，使用递归是因为“输入的字符串长度不固定”

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. 大概思路是：外循环len(digits)次，内循环两次，把新进来的字符拼在原字符后面。
3. 要注意的是ans初始化为['']

class Solution:def letterCombinations(self, digits: str) -> list:KEY = {'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']}if digits == '':return []ans = ['']for num in digits:ans = [pre+suf for pre in ans for suf in KEY[num]]return ans

新知识

1. itertools：python内置的迭代器。这道题可以先将每个数字对应的字母存入s=['abc','def']，然后直接调用itertools.product(*s)。

        import itertoolsres=[]for i in itertools.product(*s):  #*s对列表s进行解压入参,获取所有排列组合res.append(''.join(i))