JS获取字符串里最长的回文字符串

方法一

使用双指针配合枚举

/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = s => {
  const LEN = s.length
  if (LEN < 2) {
    return s
  }
  let maxStr = ''
  /**
   * @param left 
   * @param right 
   * @returns 
   */
  const findPalindrome = (left, right) => {
    while (left >= 0 && right < LEN && s[left] === s[right]) {
      left--
      right++
    }
    return s.substring(left + 1, right)
  }
  for (let i = 0; i < LEN; i++) {
    // 以i为中心判断是否是回文,如果回文是偶数则i和i+1为中心，负责i为中心。
    const strOdd = findPalindrome(i, i)
    const strEven = findPalindrome(i, i + 1)
    if (strEven.length > maxStr.length) {
      maxStr = strEven
    }
    if (strOdd.length > maxStr.length) {
      maxStr = strOdd
    }
  }
  return maxStr
}

方法二

动态规划+枚举

/**
 * @param {string} s 
 */
const longestPalindrome1 = s => {
  const LEN = s.length
  if (LEN < 2) {
    return s
  }
  // 需要保证s[l]到s[r]为回文则s[l-1]到s[r+1]也是回文，通过二维数组记录lr的回文
  const dp = []
  for (let i = 0; i < LEN; i++) {
    dp[i] = new Array(LEN).fill(false)
    dp[i][i] = true
  }
  let maxStr = s[0]
  for (let palindromeLen = 2; palindromeLen <= LEN; palindromeLen++) {
    for (let l = 0; l < LEN; l++) {
      // 右指针指向的位置应该为左指针加回文串长度减一
      let r = l + palindromeLen - 1
      if (r >= LEN) {
        break
      }
      if (s[l] === s[r]) {
        // 左指针与右指针中间最多为1个的时候可以直接判定为true， ABA 或者 aa
        if (r - l <= 2) {
          dp[l][r] = true
        } else {
          dp[l][r] = dp[l + 1][r - 1]
        }
      } else {
        dp[l][r] = false
      }

      if (dp[l][r] && r - l + 1 > maxStr.length) {
        maxStr = s.substring(l, r + 1)
      }
    }
  }
  return maxStr
}

方法三

动态规划+双指针
在这里插入图片描述
s[l][r] 依赖 s[l+1][r-1]，说明是依赖上层，所以需要把上层填满，所以r需要递增遍历固定r动l，且l需要小于r，相等的时候在初始化已经做好了。

  const LEN = s.length
  if (LEN < 2) {
    return s
  }
  // 需要保证s[l]到s[r]为回文则s[l-1]到s[r+1]也是回文，通过二维数组记录lr的回文
  const dp = []
  for (let i = 0; i < LEN; i++) {
    dp[i] = new Array(LEN).fill(false)
    dp[i][i] = true
  }
  let start = 0 , end = 0;
  // l必须小于r从第一层填起可以画三角，s[l]到s[r]依赖s[l-1]到s[r+1]
  for (let r = 1; r < LEN; r++) {
    for (let l = r - 1; l >= 0; l--) {
      if (s[l] === s[r]) {
        // 左指针与右指针中间最多为1个的时候可以直接判定为true， ABA 或者 aa
        if (r - l <= 2) {
          dp[l][r] = true
        } else {
          dp[l][r] = dp[l + 1][r - 1]
        }
      } else {
        dp[l][r] = false
      }

      if (dp[l][r] && r - l > end - start) {
        end = r;
        start = l;
      }
    }
  }
  return s.slice(start,end+1)