Problem: 17. 电话号码的字母组合

文章目录

• 思路
• 解题方法
• 复杂度
• Code

思路

这道题感受到了DFS和BFS的感觉，看上去应该是要用图的思想去做的，但是这里还是取巧了，用了一个比较简单的方法来代替DFS和BFS的递归，使用迭代的方法来解题。

解题方法

首先，要针对这个问题进行子问题的分解，比如用户输入了一个2，那么解必然是[‘a’,‘b’,‘c’]，如果用户在2的基础上输入了一个3，那么我们出现的结果必然是在2的基础上再加上3的结果。
因此，如果出现了3的结果，那么我们就需要对原有的数组进行扩展。比如3的结果是[‘d’,‘e’,‘f’]
，那么我们最终的结果肯定就是3x3 = 9，因此，我们可以直接把数组扩充len(di_ch[key])个长度，并通过sorted方法排序，排序后，由于字典序是有序的，因此可以直接进行字符串加法，通过key直接修改原有的数组。
最终时间复杂度是O（n^2）,效果整体还是很不错滴。

复杂度

• 时间复杂度:

添加时间复杂度, 示例： O(n2)O(n^2)O(n2)

• 空间复杂度:

添加空间复杂度, 示例： O(n)O(n)O(n)

Code

class Solution:di_ch ={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}def solve(self,res,info):di_ch = self.di_chif len(res) != 0:ori_len = len(res)res = res * len(di_ch[info])res = sorted(res)for index in range(0,len(res)):key = index % len(di_ch[info])res[index] = res[index] + di_ch[info][key]else:for item in di_ch[info]:res.append(item)return resdef letterCombinations(self, digits: str) -> List[str]:res = []for item in digits:res = self.solve(res,item)return res