leetcode：5. 最长回文子串

题目

给你一个字符串 s，找到 s 中最长的回文子串。

示例：

  1. 输入：s = "babad"
  2. 输出："bab"
  3. 解释："aba" 同样是符合题意的答案。
  1. 输入：s = "cbbd"
  2. 输出："bb"

解答 & 代码

解法一：中心扩展法（双指针）

外循环遍历每种可能的回文中心，然后内循环以这个回文中心为起点向两边扩展

需要注意的是，回文中心可能是一个数（回文子串长度为奇数）也可能是相邻的两个数（回文子串长度为偶数）。因此可以用两个变量 mid1、mid2 来代表回文子串中心的下标。如果 mid1==mid2，则回文中心是一个数，否则是相邻的两个数。
eg. 长为 3 的字符串，回文子串中心的下标取值 (mid1, mid2) 依次为 (0, 0)->(0,1),->(1,1)->(1,2)->(2,2)

截取 string 变量的一段用 substr()：

  • string s = "abcdefghijk"
  • string sub1 = s.substr(5)，表示从下标 5 截取到尾部，sub1 = "fghijk"

  • string sub2 = s.substr(5, 3)，表示从下标 5 截取长度为 3 的子串，sub2 = "fgh"

    1. class Solution {
    2. public:
    3.   string longestPalindrome(string s) {
    4.       int len = s.size();
    5.       if(len == 0)
    6.           return "";
    8.       int longestLeft = 0;        // 最长回文子串的左边界（含）
    9.       int longestRight = -1;        // 最长回文子串的右边界（含）
    10.       int mid1 = 0;                // 回文子串中心 1 下标
    11.       int mid2 = 0;                // 回文子串中心 2 下标
    12.       // 遍历每对回文子串中心的取值
    13.       while(mid1 < len && mid2 < len)
    14.       {
    15.           int left = mid1;        // 回文子串的左边界
    16.           int right = mid2;        // 回文子串的右边界
    17.           // 从当前回文子串中心向两边扩展
    18.           while(left >= 0 && right < len && s[left] == s[right])
    19.           {
    20.               --left;
    21.               ++right;
    22.           }
    23.           int curLen = right - left - 1;        // 当前回文子串中心对应的最长回文子串长度
    24.           int longestLen = longestRight - longestLeft + 1;    // 全局最长回文子串长度
    25.           // 更新全局最长回文子串的左、右边界
    26.           if(curLen >= longestLen)
    27.           {
    28.               longestLeft = left + 1;
    29.               longestRight = right - 1;
    30.           }
    32.           // 回文子串中心右移
    33.           if(mid1 < mid2)
    34.               ++mid1;
    35.           else
    36.               ++mid2;
    37.       }
    39.       // 返回最长回文子串
    40.       return s.substr(longestLeft, longestRight - longestLeft + 1);
    41.   }
    42. };

    复杂度分析：设字符串 s 长为 N

  • 时间复杂度 [中等] 5. 最长回文子串 - 图1：外循环遍历回文子串中心，需要迭代 2N-1 次。内循环从中心向两边扩展，时间复杂度 O(N)

  • 空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：16 ms, 在所有 C++ 提交中击败了 90.98% 的用户
  4. 内存消耗：7 MB, 在所有 C++ 提交中击败了80.74% 的用户

解法二：Manacher 算法

复杂度分析：设字符串 s 长为 N

  • 时间复杂度 O(N)
  • 空间复杂度 O(N)