javascript - 通过反转子串找到最长的回文

Question

我正在尝试找到最长的回文。我有两个指针从字符串的第一个字母开始。对于外循环中的每个字母，我遍历内循环中的所有其他字母，并使用作为起始字母(外循环)和结束字母(内循环)之间的差异的子字符串。我反转这个子字符串并检查反转版本是否与原始版本相同。这样，我知道我找到了一个回文。该算法适用于我的大多数测试用例，只有一个除外，我不明白为什么。

function longestPalindrome (str) {
  const string = str.toLowerCase();
  if (str.length < 2) return null;
  let palindrome = '';

  function stringReverser (start, end) {
    const reversed = string.substr(start, end).split('').reverse().join('');
    return reversed;
  }

  for (let i = 0; i <= string.length; i++) {
    for (let j = i; j <= string.length; j++) {
      if (string.substr(i, j) === stringReverser(i, j)) {
        if (string.substr(i,j).length > palindrome.length) {
          palindrome = string.substr(i,j);
        }
      }
    }
  }

  if (!palindrome) return null;
  return palindrome;
}

let result1 = longestPalindrome('My mom is called annnna')
let result2 = longestPalindrome('My dad is a racecar athelete')
let result3 = longestPalindrome('That trip with a kayak was quite an adventure!')

console.log(result1)
console.log(result2)
console.log(result3)// should return ' kayak ' but returns 't t' instead.

Answer 1

我建议抽象出选定的子字符串，并使用 isPalendrome 函数:

function longestPalindrome (str) {
  const inputString = str.toLowerCase();
  if (str.length < 2) return null;
  let longestPalindrome = '';

  function isPalendrome(strParam) {
    return strParam === strParam.split('').reverse().join('');
  }

  for (let i = 0; i <= inputString.length; i++) {
    for (let j = i; j <= inputString.length; j++) {
      const thisStr = inputString.slice(i, j);
      if (!isPalendrome(thisStr)) continue;
      if (thisStr.length > longestPalindrome.length) longestPalindrome = thisStr;
    }
  }
  return longestPalindrome || null;
}

let result1 = longestPalindrome('My mom is called annnna')
let result2 = longestPalindrome('My dad is a racecar athelete')
let result3 = longestPalindrome('That trip with a kayak was quite an adventure!')

console.log(result1)
console.log(result2)
console.log(result3)