为何allConstruct()空间复杂度为O(m)？与countConstruct的差异疑问

架构老林

2026-8-24

allConstruct与countConstruct的空间复杂度疑问

以下实现源自某YouTube视频，本文探讨两个字符串拼接函数的空间复杂度问题：

target：目标字符串
wordBank：用于拼接的字符串数组

allConstruct函数分析

函数说明

示例调用：allConstruct('purple', ['purp', 'p', 'ur', 'le', 'purpl'])
该函数用于找出wordBank中所有能拼接成target的字符串组合。

代码实现

const allConstruct = (target, wordBank) => {
  for (let word of wordBank) {
    if (target.indexOf(word) === 0) {
      const suffix = target.slice(word.length);
      const suffixWays = allConstruct(suffix, wordBank);
      const targetWays = suffix.map(way => [ word, ...way ]);
      result.push(...targetWays);
    }
  }
}

视频给出的空间复杂度

O(M) | M = target.length

疑问点

这个结论在最坏情况（需要M个字符拼接目标字符串，对应M个递归栈帧）下看似合理，但存在两个疑问：

为什么没考虑每个递归调用中suffix = target.slice(word.length)生成的字符串空间？每个调用可能存储长度为M的字符串。
为什么没考虑targetWays = suffix.map(way => [ word, ...way ])生成的二维数组空间？

是不是因为视频把空间复杂度简化为栈帧大小，即认定为O(m) | m = 递归调用的栈帧数量？

countConstruct函数分析

如果上述简化逻辑成立，那视频中前一个示例countConstruct的空间复杂度认定就存在矛盾：

函数说明

该函数用于计算wordBank拼接成target的方式总数。

代码实现

const countConstruct = (target, wordBank) => {
  if (target === '') return 1;
  let totalCount = 0;

  for (let word of wordBank) {
    if (target.indexOf(word) === 0) {
      const numWaysForRest = countConstruct(target.slice(word.length), wordBank);
      totalCount += numWaysForRest;
    }
  }
  return totalCount;
}