JS递归判断字符串能否由词库拼接时报调用栈溢出错误如何解决

核心问题1：字符串截取逻辑错误，导致无限递归 #

你当前的shorterTargetString = targetString.slice(0, dictionary[i].length)逻辑是取出匹配到的前缀本身，而非「去掉前缀后的剩余字符串」。比如匹配到长度为3的fur时，截取到的还是前3个字符fur，递归调用时入参永远是fur，永远触发不了空字符串的基线条件，最终导致调用栈溢出。
正确的截取逻辑应该是从单词长度的位置开始截取到字符串末尾：targetString.slice(dictionary[i].length)。

核心问题2：递归返回逻辑错误，提前终止匹配尝试 #

你当前的代码只要找到第一个匹配的前缀，就直接返回递归调用的结果，不管这个结果是true还是false。如果第一个匹配的前缀后续无法完全拼接成目标字符串，代码也不会再尝试其他可能匹配的前缀，会直接返回错误结果。
正确的逻辑是：如果递归调用返回true，才向上返回true；如果返回false，继续遍历词库的下一个单词，所有单词都尝试失败后再返回false。

修正后的代码 #

let targetString = "furniture";
let dictionary = ["fur", "ure", "nit"];
const tableData = {};

const canConstructRecursive = (targetString, dictionary) => {
  // 基线条件：空字符串表示可以拼接成功
  if (targetString == "") {
    return true
  }

  for (let i = 0; i < dictionary.length; i++) {
    if (targetString.indexOf(dictionary[i]) == 0) {
      // 截取去掉当前前缀后的剩余字符串
      const shorterTargetString = targetString.slice(dictionary[i].length);
      // 只有子问题返回true时才向上返回true，否则继续尝试其他单词
      if (canConstructRecursive(shorterTargetString, dictionary)) {
        return true;
      }
    }
  }
  // 所有单词都尝试失败才返回false
  return false;
}

console.log(canConstructRecursive(targetString, dictionary));

可选优化：增加记忆化逻辑避免重复计算 #

你定义的tableData可以用来存储已经计算过的子串结果，大幅降低长字符串/大词库场景下的时间消耗：

const canConstructMemo = (targetString, dictionary, memo = {}) => {
  if (targetString in memo) return memo[targetString];
  if (targetString == "") return true;

  for (let i = 0; i < dictionary.length; i++) {
    if (targetString.indexOf(dictionary[i]) == 0) {
      const shorterTargetString = targetString.slice(dictionary[i].length);
      if (canConstructMemo(shorterTargetString, dictionary, memo)) {
        memo[targetString] = true;
        return true;
      }
    }
  }
  memo[targetString] = false;
  return false;
}

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