如何使用递归计算字符串中的所有回文? [英] How to count all the palindromes in a string using recursion?

问题描述

我有一个递归函数，用于检查字符串是否是回文，但是我的作业要求我计算字符串中回文的数量(例如，皮艇有2个).

I have a recursive function that checks if a string is a palindrome, but my assignment asks me to count the number of palindromes in a string (for example kayak has 2).

我对如何实现计算回文数的递归函数感到非常困惑.这是我当前的代码:

I'm really confused about how I can implement a recursive function that counts the number of palindromes. Here's my current code:

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;
  }
}

推荐答案

我认为接受的答案实际上不起作用.除非它们位于字符串的中心，否则它将不计算回文，并且只要它们以相同的字母开头和结尾，就将计算不是回文的子字符串.来自某些性能"的答案可能会起作用，但我认为这将导致检查很多不需要检查的字符串.这是我想出的，我认为它适用于我添加的额外测试.

I think the accepted answer does not actually work. It will not count palindromes unless they are centered in the string and will count substrings that are not palindromes if as long as they start and end with the same letter. The answer from CertainPerformance would probably work but I think it would result in checking a lot of strings that don't need to be checked. Here's what I came up with, I think it works for the extra tests I've added.

function countPalindromes(string) {
    if (string.length <= 1) {
    return 0;
    }

    count = 0

    for ( var i = 0; i < string.length; i++  ) {
    count += countPalindromesCenteredAt(string, i)
    count += countPalindromesCenteredAfter(string, i)
    }

    return count
}

function countPalindromesCenteredAt(string, i) {
    count = 0
    for ( var j = 1; i-j>=0 && i+j < string.length; j++  ) {
    if (string.charAt(i-j) === string.charAt(i+j)) {
        count += 1
    }
    else {
        return count
    }
    }

    return count
}

function countPalindromesCenteredAfter(string, i) {
    count = 0
    
    for ( var j = 1; i-j>=0 && i+j < string.length; j++  ) {
    if (string.charAt(i-j+1) === string.charAt(i+j)) {
        count += 1
    }
    else {
        return count
    }
    }

    return count
}

console.log(countPalindromes("kayak"));
console.log(countPalindromes("aya"));
console.log(countPalindromes("kayakcanoe"));
console.log(countPalindromes("kcanoek"));

这篇关于如何使用递归计算字符串中的所有回文?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！