javascript - 计算一个字符串有多少个子串是回文

Question

我目前正在尝试计算给定字符串中有多少个子字符串是回文。

当给定字符串 aabaa 时，预期输出为 5 但是我的代码输出 4。我不太清楚为什么，谁能帮我解决这个问题？

我的代码:

function countPalindromesInString(s) {
    let count = 0;

    if (s === s.split('').reverse().join('')) {
        count += 1;
    }

    let testStr = '';
    for (let i = 0; i < s.length; i++) {
        testStr += s[i];

        if (testStr === testStr.split('').reverse().join('')) {
            count += 1;
        }
    }
    return count;
}

Answer 1

我不确定为什么您期望输入 aabaa 的输出为 5。在我看来，如果将单个字母视为回文，则输出应为 9，否则结果应为 4: "aa", "aa", “aba”, “aabaa”。您的代码仅从左到右计数，并且还对完整的 5 个字母字符串进行两次计数，一次在开头，此处:

if (s === s.split('').reverse().join('')) {
计数 += 1；
}

一次在 for 循环中 for case i=4;

这是您问题的解决方案:

function countPalindromesInString(s) {
    let count = 0;  //or s.length if you chose to count single letters as palindrome
    let subString;

    for (let i = 1; i < s.length; i++) {
      for(let j = 0; j < s.length - i; j++) {
        subString = s.substring(j, j+i+1);
        if(subString === subString.split('').reverse().join('')) {
            count += 1;
        }
      }
    }
    return count;
}

稍后编辑:

如果我们想计算字符串中唯一的回文，我们可以将找到的回文存储在一个数组中，每次找到另一个回文时，我们检查它是否以前添加过:

function countPalindromesInString(s) {
    let subStrings = [];

    for (let i = 0; i < s.length; i++) {
      for(let j = 0; j < s.length - i; j++) {
        let subString = s.substring(j, j+i+1);
        if(subString === subString.split('').reverse().join('') && !subStrings.includes(subString)) {
          subStrings.push(subString);
        }
      }
    }
    return subStrings.length;
}