[算法刷题]非递归解 电话号码的字母组合

Posted on by hackdl

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

文章目录

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

思路

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

解题方法

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

复杂度

  • 时间复杂度:

添加时间复杂度, 示例：

  • 空间复杂度:

添加空间复杂度, 示例：

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_ch
        if 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 res

    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        for item in digits:
            res = self.solve(res,item)
        return res

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: