LeetCode「分割回文串II」暴力递归解法的时间与空间复杂度咨询

时间复杂度 #

最坏时间复杂度为 O(n × 2ⁿ)，推导逻辑：

• 长度为n的字符串共有n-1个可切分间隙，每个间隙可选择切或不切，总共有 2ⁿ⁻¹ 种不同的分割方案，暴力递归会遍历所有可能的分割方案。
• 对每种分割方案，需要验证所有子串是否为回文，单次回文验证的时间和子串长度成正比，单种分割方案的所有回文验证总耗时为O(n)。
• 无记忆化的递归存在大量重复子问题调用，同一段[start, end]区间可能被多次验证是否为回文，这部分开销也被包含在上述上界中。
  如果遇到极端最坏场景（比如字符串所有字符均不相同，仅单字符为合法回文），实际运行耗时会趋近这个上界。

空间复杂度 #

空间复杂度为 O(n)：

• 仅递归栈占用额外空间，最坏情况下每次仅切出1个字符，递归栈的最大深度为n。
• 回文验证函数没有使用额外存储空间，无其他额外开销。

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