javascript - 字符串中最长的回文

Question

我编写了以下函数来查找字符串中最长的回文。它工作正常，但不适用于“noon”或“redder”之类的词。我摆弄并更改了 for 循环中的第一行:

var oddPal = centeredPalindrome(i, i);

到

var oddPal = centeredPalindrome(i-1, i);

现在可以了，但我不清楚原因。我的直觉是，如果您正在检查一个奇数长度的回文，它的开头将有一个额外的字符(我将其用白板写下来，这就是我得出的结论)。我的推理是否正确？

var longestPalindrome = function(string) {

  var length = string.length;
  var result = "";

  var centeredPalindrome = function(left, right) {
    while (left >= 0 && right < length && string[left] === string[right]) {
      //expand in each direction.
      left--;
      right++;
    }

    return string.slice(left + 1, right);
  }; 

  for (var i = 0; i < length - 1; i++) {
    var oddPal = centeredPalindrome(i, i); 
    var evenPal = centeredPalindrome(i, i);

    if (oddPal.length > result.length)
      result = oddPal;
    if (evenPal.length > result.length)
      result = evenPal;
  }

  return "the palindrome is: " + result + " and its length is: " + result.length;
};

更新:Paul的真棒之后answer ，为了清楚起见，我认为更改两个变量是有意义的:

var oddPal  = centeredPalindrome(i-1, i + 1);
var evenPal = centeredPalindrome(i, i+1);

Answer 1

你有它倒退 - 如果你输出“奇数”回文(用你的修复)你会发现它们实际上是偶数长度。

想象一下“中午”，从第一个“o”(左和右)开始。匹配，然后将它们都移动 - 现在您正在比较第一个“n”和第二个“o”。不好。但是通过修复，您开始比较两个“o”，然后移动到两个“n”。

示例(使用 var oddPal = centeredPalindrome(i-1, i); 修复):

var longestPalindrome = function(string) {

  var length = string.length;
  var result = "";

  var centeredPalindrome = function(left, right) {
    while (left >= 0 && right < length && string[left] === string[right]) {
      //expand in each direction.
      left--;
      right++;
    }

    return string.slice(left + 1, right);
  };

  for (var i = 0; i < length - 1; i++) {
    var oddPal = centeredPalindrome(i, i + 1);

    var evenPal = centeredPalindrome(i, i);

    if (oddPal.length > 1)
      console.log("oddPal: " + oddPal);
    if (evenPal.length > 1)
      console.log("evenPal: " + evenPal);

    if (oddPal.length > result.length)
      result = oddPal;
    if (evenPal.length > result.length)
      result = evenPal;
  }
  return "the palindrome is: " + result + " and its length is: " + result.length;
};

console.log(
  longestPalindrome("nan noon is redder")
);