javascript - 如何使用递归计算字符串中的所有回文？

Question

我有一个递归函数来检查字符串是否为回文，但我的作业要求我计算字符串中回文的数量(例如 kayak 有 2 个)。

我真的很困惑如何实现一个计算回文数的递归函数。这是我当前的代码:

function isPalindrome(string) {
  if (string.length <= 1) {
    return true;
  }

  let [ firstLetter ] = string;
  let lastLetter = string[string.length - 1];

  if (firstLetter === lastLetter) {
    let stringWithoutFirstAndLastLetters = string.substring(1, string.length - 1);
    return isPalindrome(stringWithoutFirstAndLastLetters);
  } else {
    return false;
  }
}

Answer 1

当函数得到回文时很容易:

1. 记录输入
2. 没有边缘再试一次
3. 输入不超过三个字符时停止

"kayak" -> "aya"

如果输入不是回文，请递归地尝试“两端”，例如使用 "kayam" 尝试同时使用 "kaya" 和 "ayam" 并继续...

当字符串为 3 个(或更少)字符时，我们将停止递归。单个字符不是回文，检查两个或三个字符的字符串是否是回文是微不足道的。

                      kayam
                        |
                  +-------------+
                  |             |
                 kaya          ayam
                  |             |
              +-------+     +--------+
              |       |     |        |
             kay     aya   aya      yam

---

const reverse =
  ([...xs]) =>
    xs.reverse().join("");

const is_palindrome =
  a =>
      a.length === 1  ? false
    : a.length <= 3   ? a[0] === a[a.length-1]
                      : a === reverse(a);

const find_palindromes = str => {
  const scan =
    (x, xs = []) =>
        x.length <= 3     ? xs.concat(is_palindrome(x) ? x : [])
      : is_palindrome(x)  ? xs.concat
                              ( x
                              , scan(x.slice(1, -1))
                              )
                          : xs.concat
                              ( scan(x.slice(0, -1))
                              , scan(x.slice(1))
                              );

  return [...new Set(scan(str))];
};


console.log(find_palindromes("kayak").join());
console.log(find_palindromes("kayakkayak").join());
console.log(find_palindromes("kayakcanoe").join());
console.log(find_palindromes("kayam").join());
console.log(find_palindromes("appal").join());
console.log(find_palindromes("madamimadam").join());
console.log(find_palindromes("madamimadamkayak").join());