一、題目來(lái)源：leetcode第5題

二、題目描述

給你一個(gè)字符串 s毅弧，找到 s 中最長(zhǎng)的回文子串擅羞。

如果字符串的反序與原始字符串相同，則該字符串稱為回文字符串。

示例 1：

輸入： s = "babad" 輸出： "bab" 解釋： "aba" 同樣是符合題意的答案躁锁。

示例 2：

輸入： s = "cbbd" 輸出： "bb"

提示：

• 1 <= s.length <= 1000
• s 僅由數(shù)字和英文字母組成

三、解題

3.1 解法一

1. 思路

   定義兩個(gè)指針卵史，使用中心擴(kuò)展法來(lái)找到回文子串战转。遍歷字符串中的每個(gè)字符，以當(dāng)前字符為中心向兩邊擴(kuò)展以躯，分別檢查奇數(shù)長(zhǎng)度和偶數(shù)長(zhǎng)度的回文子串槐秧。

2. 解法

/**
 * 在給定的字符串中找到最長(zhǎng)的回文子串。
 *
 * @param {string} s - 輸入字符串忧设。
 * @return {string} - 找到的最長(zhǎng)回文子串刁标。
 */
const longestPalindrome = function(s) {
  let res = '';

  for (let i = 0; i < s.length; i++) {
    const odd = expandAroundCenter(s, i, i);
    const even = expandAroundCenter(s, i, i + 1);
    const longest = odd.length > even.length ? odd : even;
    if (longest.length > res.length) {
      res = longest;
    }
  }
  return res;

  /**
   * 在給定的字符串中找到最長(zhǎng)的回文子串。
   *
   * @param {string} s - 輸入字符串址晕。
   * @param {number} l - 要檢查的子串的左索引膀懈。
   * @param {number} r - 要檢查的子串的右索引。
   * @return {string} - 找到的最長(zhǎng)回文子串谨垃。
 */
  function expandAroundCenter(s, l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      l--;
      r++;
    }
    return s.substring(l + 1, r);
  }
};

3. 時(shí)間復(fù)雜度

由于遍歷字符串需要 O(n) 的時(shí)間启搂，而在每個(gè)位置上進(jìn)行中心擴(kuò)展需要 O(n) 的時(shí)間硼控，因此總體時(shí)間復(fù)雜度為 O(n^2) 。

4. 空間復(fù)雜度

算法只使用了常數(shù)個(gè)變量來(lái)保存中間結(jié)果胳赌，沒有使用額外的數(shù)據(jù)結(jié)構(gòu)或數(shù)組牢撼。因此，空間復(fù)雜度可以表示為O(1) 疑苫。

3.2 解法二

1. 思路

馬拉車算法（Manacher's Algorithm）熏版，基本思想是利用回文串的對(duì)稱性來(lái)減少不必要的重復(fù)計(jì)算。它通過(guò)維護(hù)一個(gè)回文半徑數(shù)組捍掺，以及一個(gè)當(dāng)前已知的最右回文邊界纳决，來(lái)快速計(jì)算每個(gè)字符位置的回文半徑。該算法的具體實(shí)現(xiàn)比較復(fù)雜乡小，但可以在線性時(shí)間內(nèi)找到最長(zhǎng)回文子串阔加。

2. 解法

/**
 * 在給定的字符串中找到最長(zhǎng)的回文子串。
 *
 * @param {string} s - 輸入字符串满钟。
 * @return {string} - 找到的最長(zhǎng)回文子串胜榔。
 */
const longestPalindrome = function(s) {
  // 預(yù)處理字符串，在每個(gè)字符之間插入特殊字符
  const preprocessString = function(s) {
    let result = '^';
    for (let i = 0; i < s.length; i++) {
      result += '#' + s.charAt(i);
    }
    result += '#$';
    return result;
  };
  // 預(yù)處理字符串
  const processedString = preprocessString(s);
  const n = processedString.length;
  const palindromeRadius = new Array(n).fill(0); // 回文半徑數(shù)組
  let center = 0; // 當(dāng)前已知的最右邊回文子串的中心
  let right = 0; // 當(dāng)前已知的最右邊回文子串的右邊界

  for (let i = 1; i < n - 1; i++) {
    // 利用對(duì)稱性得到一部分回文信息
    if (i < right) {
      const mirror = 2 * center - i;
      palindromeRadius[i] = Math.min(right - i, palindromeRadius[mirror]);
    }

    // 中心擴(kuò)展法檢查以當(dāng)前字符為中心的回文子串
    while (
      processedString[i + 1 + palindromeRadius[i]] ===
      processedString[i - 1 - palindromeRadius[i]]
    ) {
      palindromeRadius[i]++;
    }

    // 更新最右邊回文子串的中心和右邊界
    if (i + palindromeRadius[i] > right) {
      center = i;
      right = i + palindromeRadius[i];
    }
  }

  // 找到最長(zhǎng)回文子串的中心位置和長(zhǎng)度
  let maxRadius = 0;
  let centerIndex = 0;
  for (let i = 1; i < n - 1; i++) {
    if (palindromeRadius[i] > maxRadius) {
      maxRadius = palindromeRadius[i];
      centerIndex = i;
    }
  }

  // 根據(jù)中心位置和長(zhǎng)度獲取原始字符串中的最長(zhǎng)回文子串
  const start = (centerIndex - maxRadius) / 2;
  const end = start + maxRadius;
  return s.substring(start, end);
};

3. 時(shí)間復(fù)雜度

   1. 預(yù)處理字符串的時(shí)間復(fù)雜度為 O(n)湃番，其中 n 是字符串的長(zhǎng)度夭织。在預(yù)處理過(guò)程中，我們?cè)诿總€(gè)字符之間插入特殊字符（通常是#）吠撮，以處理偶數(shù)長(zhǎng)度的回文子串尊惰。

   2. 馬拉車算法的主要部分是一個(gè)線性的循環(huán)，遍歷預(yù)處理后的字符串泥兰。在該循環(huán)中弄屡，我們使用對(duì)稱性和中心擴(kuò)展法來(lái)計(jì)算每個(gè)字符作為回文子串中心時(shí)的回文半徑。

      1. 對(duì)稱性的計(jì)算時(shí)間復(fù)雜度為 O(n)鞋诗。我們維護(hù)兩個(gè)變量 center 和 right膀捷，并利用已知回文子串的對(duì)稱性來(lái)更新回文半徑。
      2. 中心擴(kuò)展法的時(shí)間復(fù)雜度為 O(n)削彬。我們?cè)诿總€(gè)字符為中心時(shí)全庸，向左右兩側(cè)擴(kuò)展并檢查回文性質(zhì)。

   3. 因此融痛，整個(gè)算法的時(shí)間復(fù)雜度為 O(n) 壶笼。

4. 空間復(fù)雜度

   1. 預(yù)處理后的字符串需要 O(n) 的額外空間，因?yàn)槲覀冊(cè)诿總€(gè)字符之間插入特殊字符雁刷。
   2. 回文半徑數(shù)組需要 O(n) 的額外空間覆劈，用于存儲(chǔ)每個(gè)字符作為回文子串中心時(shí)的回文半徑。
   3. 因此，總體空間復(fù)雜度為 O(n) 墩崩。

四氓英、知識(shí)點(diǎn)

雙指針?biāo)惴?/strong>是一種常用的技巧，在解決多種問題時(shí)都可以應(yīng)用鹦筹。雙指針的使用方式分以下3種：