带记忆化的单词拆分递归算法时间复杂度为何仍为指数级？

首先明确结论：你给出的代码如果仅需要返回任意一个合法拆分，且词典不包含空串的话，加了记忆化之后的时间复杂度确实属于多项式级，最坏为O(n²)~O(n³)（n为输入字符串长度）。如果有从业者认为复杂度仍然是指数级，大概率是混淆了不同的问题场景或者实现细节：

常见的混淆点解释 #

• 混淆「返回单个拆分」和「返回所有拆分」的需求差异
  这是最常见的原因。如果需求是返回所有合法的拆分结果，哪怕加了记忆化，复杂度也必然是指数级。举个最简单的例子：输入字符串是n个连续的a，词典为{"a", "aa"}，此时合法拆分的数量等于斐波那契数列的第n+1项，本身就是指数级增长的，你需要生成并返回所有这些拆分，时间和空间复杂度自然是指数级。
  而你的代码只要找到第一个合法拆分就直接返回，不需要遍历所有可能性，所以不存在这个问题。

• 忽略字符串操作的隐性成本，但仍然属于多项式级
  你的代码用字符串切片作为记忆化的key，每次生成切片 s[i:]、计算字符串哈希、判断字符串是否在memo中，都需要O(k)的时间（k为当前字符串的长度），最坏情况下总时间会达到O(n³)，但这仍然是多项式级，和指数级有本质区别。
  如果想优化这部分成本，可以把递归参数改为原字符串的起始索引，用索引作为记忆化的key，就能把字符串操作的成本降为O(1)，总时间复杂度优化到O(n²)。

• 无记忆化的实现确实是指数级
  如果去掉记忆化，同一个后缀子串会被重复计算非常多次，最坏情况下分支因子为O(n)，递归深度为O(n)，复杂度确实是指数级，这也是很多人对这个问题的固有印象，可能因此误判了加记忆化后的复杂度。

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