javascript - 如何在 for 循环中正确调用递归函数？

Question

我正在尝试实现一个以参数为参数的方法:目标 string 和一个包含 string 值的 array。目标是检查是否可以用数组的值构造给定的目标字符串。数组中的单词可以根据需要使用多次。示例:

console.log(canConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"])); // suppose to return true

正如我们所见，通过连接"abc"和"def"，我们得到了"abcdef"的目标字符串 这是我的函数实现:

const canConstruct = function (target, wordBank) {
  if (target === "") return true;
  console.log(target);
  for (let word of wordBank) {
    if (target.startsWith(word)) {
      return canConstruct(target.replace(word, ""), wordBank);
    }
  }

  return false;
};  

第 2 行是此递归函数的基本情况，然后通过遍历数组检查它是否以数组元素开头，如果为真则删除该特定子数组并使用新目标字符串和旧数组再次调用该函数，如果 false 继续迭代整个函数，直到它达到基本情况。所以再次使用前面的例子:

console.log(canConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]));  // return false

我弄错了，通过调试我可以看到自第一次递归调用以来它没有迭代整个数组。我得到以下输出:

abcdef
cdef
ef
false

Answer 1

在我看来，这里有一个悬而未决的问题。我们可以多次使用子字符串还是每次只使用一次？也就是应该

canConstruct ("abcabc", ["ab", "abc", "cd", "def", "abcd"])

返回 true 因为我们可以将它分解为 abc-abc，使用第二个条目两次？

或者它应该返回 false 因为我们已经用完了开始的 abc 吗？

这两个片段是您的技术的变体，具有不同的风格。

第一个假设我们可以根据需要经常使用我们的子串:

const canConstruct = (word, words) => 
  word.length == 0
    ? true
    : words .some (
        (w) => word .startsWith (w) && canConstruct (word .replace (w, ''), words)
      )

console .log (canConstruct ("abcdef", ["ab", "abc", "cd", "def", "abcd"]))  //=> true
console .log (canConstruct ("abcddc", ["ab", "abc", "cd", "def", "abcd"]))  //=> false
console .log (canConstruct ("abcabc", ["ab", "abc", "cd", "def", "abcd"]))  //=> true

第二个说我们每个只能使用一次:

const removeFirst = (x, xs, i = xs.indexOf(x)) =>
  i < 0
    ? [... xs]
    : [... xs .slice (0, i), ... xs .slice (i + 1)]

const canConstruct = (word, words) => 
  word.length == 0
    ? true
    : words .some (
        (w) => word .startsWith (w) && canConstruct (word .replace (w, ''), removeFirst(w, words))
      )

console .log (canConstruct ("abcdef",    ["ab", "abc", "cd", "def", "abcd"]))         //=> true
console .log (canConstruct ("abcddc",    ["ab", "abc", "cd", "def", "abcd"]))         //=> false
console .log (canConstruct ("abcabc",    ["ab", "abc", "cd", "def", "abcd"]))         //=> false
console .log (canConstruct ("abcabc",    ["ab", "abc", "cd", "abc", "def", "abcd"]))  //=> true
console .log (canConstruct ("abcabcabc", ["ab", "abc", "cd", "abc", "def", "abcd"]))  //=> false

这里我们使用辅助函数 removeFirst，它在删除给定值的第一个实例后返回数组的副本。