Leetcode电话号码字母组合递归解法的时间与空间复杂度计算

时间复杂度 #

计算逻辑如下：

• 设输入数字字符串digits的长度为n，其中有a个数字对应3个字母（2、3、4、5、6、8），b个数字对应4个字母（7、9），满足a + b = n
• 所有可能的字母组合总数为3^a * 4^b，最坏情况所有数字都是7/9，总组合数为4^n
• 每个组合需要生成长度为n的字符串，单次字符串拼接的时间开销为O(n)
• 二者相乘得到总时间复杂度为O(n * 3^a * 4^b)，最坏情况为O(n * 4^n)

举个简单例子验证：输入为"23"时，n=2，a=2、b=0，总组合数为9，每个字符串长度为2，总操作量级符合O(2 * 3^2)的计算结果。

空间复杂度 #

按两种统计口径分别说明：

• 包含结果存储的总空间：需要存储所有3^a * 4^b个长度为n的字符串，总空间为O(n * 3^a * 4^b)，最坏情况为O(n * 4^n)
• 不计结果存储的额外空间：仅统计递归栈的开销，递归深度等于输入字符串长度n，额外空间复杂度为O(n)

内容的提问来源于stack exchange，提问作者Aadi