0

我正在解决这个 Leetcode 问题 - “给定一个包含 2-9 数字的字符串，返回该数字可以代表的所有可能的字母组合。以任何顺序返回答案。

下面给出了数字到字母的映射（就像在电话按钮上一样）。请注意，1 不映射到任何字母。”

在此处输入图像描述

这是我能够理解的问题的递归解决方案，但我无法弄清楚解决方案的时间和空间复杂度。

if not len(digits):
        return []
    
    res = []
    
    my_dict = {
        '2':'abc',
        '3':'def',
        '4':'ghi',
        '5':'jkl',
        '6':'mno',
        '7':'pqrs',
        '8':'tuv',
        '9':'wxyz'
    }
    
    if len(digits) == 1:
        return list(my_dict[digits[0]])
    
    my_list = my_dict[digits[0]] #string - abc
    
    for i in range(len(my_list)): # i = 0,1,2
        for item in self.letterCombinations(digits[1:]):
            print(item)
            res.append(my_list[i] + item) 
    return res

有关计算此解决方案的时间和空间复杂度的任何帮助或解释都会有所帮助。谢谢你。

4

1 回答 1

0

对于某些组合问题，时间和空间复杂度可能会受到输出大小的支配。查看循环和函数调用，函数中所做的工作是一个字符串连接和一个附加输出的每个元素。还有多达 4 次重复的递归调用self.letterCombinations(digits[1:])：假设这些没有被缓存，我们需要添加额外的重复工作。

我们可以写一个公式来计算当 时解决问题所需的运算次数len(digits) == n。如果 T(n) 是步数，A(n) 是答案数组的长度，我们得到T(n) = 4*T(n-1) + n*A(n) + O(1)。我们在 A(n) 上得到一个额外的 n 乘法因子，因为字符串连接是线性时间；一个带有列表的实现，并且str.join()会避免这种情况。

由于 A(n) 的上限为 4^n，并且 T(1) 是一个常数，因此给出T(n) = O(n * (4^n)); 这里的空间复杂度也是O(n * (4^n))，给定 4^n 个长度为 n 的字符串。

复杂性分析的一个可能令人困惑的部分是，除非另有说明，否则它通常是最坏情况分析。这就是我们在这里使用 4 而不是 3 的原因：如果任何输入可以给出 4^n 个结果，我们使用那个数字，即使许多数字输入会给出更接近 3^n 个结果。

于 2021-09-08T05:30:18.750 回答