每日一算--最长回文子串

808 阅读3分钟

题目

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例1

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例2

输入: "cbbd"
输出: "bb"

示例3

输入: "cbad"
输出: ""

日常找规律

一句话解释回文的意思是正着念和倒着念一样,如:上海自来水来自海上,山西运煤车煤运西山等,瞬间感觉自己在听郭德纲相声

  • 暴力法将选出所有子字符串可能的开始和结束位置,并检验它是不是回文。
  • 改进暴力法,我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑 “ababa” 这个示例。如果我们已经知道“bab”是回文,那么很明显,“ababa” 一定是回文,因为它的左首字母和右尾字母是相同的得出动态方程
  • P(i,i)=true P(i,i+1)=(Si == Si+ 1)

实现方式

暴力搜索

时间复杂度 O(N^3)

const longestPalindrome = function(s) {
  if (!s) return ''
  let longest = s[0]
  let str, i, j, len
  const isPalindrom = function (left, right) {
    while (left < right && s[left] === s[right]) {
      left++;
      right--;
    }
    return left >= right;
  }
  for (len = 2; len <= s.length; len++) {
    for (i = 0; i < s.length; i++) {
      j = i + len - 1;
      if (isPalindrom(i, j)) {
        str = s.slice(i, j + 1);
        if (longest.length < str.length) longest = str;
      }
    }
  }
  return longest
}

动态规划

时间复杂度 O(N^3) 空间复杂度 O(N^2)

回文字符串定位为: dp(start,end)

  • start是回文字符串的起始位置
  • end 是回文字符串的截止位置
  • 回文字符串要满足的基本条件为: str[start] == str[end] 并且 dp(start+1,end-1) 也为回文字符串
  • 边界条件为:
    start-end=0, 例如:"a"
    start-end=1 && str[start] == str[end],例如:"aa","bb"
const longestPalindrome = function(s) {
  let i, j, len
  const isPalindrom = new Array(s.length);
  for (i = 0; i < s.length; i++) {
    isPalindrom[i] = new Array(s.length).fill(false);
  }
  let maxLen = 1, longestBegin = 0;
  for (i = 0; i < s.length; i++) {
    isPalindrom[i][i] = true;
    if (i < s.length - 1 && s[i] === s[i + 1]) {
      isPalindrom[i][i + 1] = true;
      maxLen = 2;
      longestBegin = i;
    }
  }
  for (len = 3; len <= s.length; len++) {
    for (i = 0; i < s.length; i++) {
      j = len + i - 1;
      if (s[i] === s[j] && isPalindrom[i + 1][j - 1]) {
        isPalindrom[i][j] = true;
        maxLen = len;
        longestBegin = i;
      }
    }
  }
  return s.slice(longestBegin, longestBegin + maxLen);
}

优化降低空间复杂度

空间复杂度降到 O(1),只存找到的最长回文串即可。枚举轴心位置,并进行扩展。如果是回文,则轴心两边的字符应该对称相等。需要考虑到长度奇偶情况的不同,如果是奇数长度,轴心就是一个字符;如果是偶数长度,轴心则不在字符串中

const longestPalindrome = function(s) {
  if (!s) return '';
  let longest = s[0];
  let expandAroundCenter = function (left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return s.slice(left + 1, right);
  }
  for (let i = 0; i < s.length; i++) {
    let odd = expandAroundCenter(i, i);
    if (odd.length > longest.length) longest = odd;
    let even = expandAroundCenter(i, i + 1);
    if (longest.length < even.length) longest = even;
  }
  return longest;
}

优化降低时间复杂度

相比降低空间复杂度,降低时间复杂度要难得多。这里有一个 O(N) 时间复杂度的算法,叫做 Manacher 算法

const longestPalindrome = function(s) {
  s = '^#' + s.split('').join('#') + '#$';
  let radius = new Array(s.length).fill(0);
  let C = 0, centerIndex = 0, maxRight = 0, maxLen = 0;

  for (let i = 1; i < s.length - 1; i++) {
    # 计算初始回文半径, i' = 2 * C - i
    radius[i] = (maxRight > i) ? Math.min(maxRight - i, radius[2 * C - i]) : 0;
    # 扩展半径
    while (s[i + 1 + radius[i]] && s[i - 1 - radius[i]] && s[i + 1 + radius[i]] === s[i - 1 - radius[i]]) radius[i]++;
    # 更新当前搜索的最大右边界和位置
    if (i + radius[i] > maxRight) {
      C = i;
      maxRight = i + radius[i];
    }
    # 更新最大回文串长度及位置
    if (maxLen < radius[i]) {
      maxLen = radius[i];
      centerIndex = i;
    }
  }
  return s.slice((centerIndex - maxLen), (centerIndex + maxLen + 1)).split('#').join('');
}

总结