5. Longest Palindromic Substring

Posted on | In | 浏览 次
Words count in article: 682 | Reading time ≈ 3

题目

  • Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
  • Example 
    1
    2
    3
    Input: "babad"
    Output: "bab"
    Note: "aba" is also a valid answer.

解题

解题思路

  • 这道题要求我们找出一个字符串里面的最长回文串，而什么是回文串呢，回文串就是正反读都是一样的字符串。对于这个问题，解决方法就是找一个字符，以其为中心，向两边扩展寻找出最长的回文串，该算法的时间复杂度为$O(n)$,当然还需要注意一点的就是回文串的长度可奇可偶，如长度为奇数的回文串”aba”以及长度为偶数的回文串”baab”，因此在以某个字符为中心的向两边扩展的需要额外的考虑。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() <= 1)	return s;
        int len = 0;
        int id = 0;
        for(int i = 0; i < s.size() - 1; ++i) {
            if(s[i] == s[i+1]) 
                searchLongestPalindrome(i, i+1, id, len, s);
            searchLongestPalindrome(i, i, id, len, s);
        } 
        return s.substr(id, len);
    }

    void searchLongestPalindrome(int left, int right, int &id, int &len, string s) {
        while(left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        int tmp = right - left - 1;
        if(tmp >= len) {
            id = left + 1;
            len = tmp;
        }
    }
};

更优解法

  • 对于解决回文子串问题，有一种更加高效的算法，拉车算法(Manacher‘s Algorithm)是用来查找一个字符串的最长回文子串的线性方法，其时间复杂度仅为$O(n)$
    • 此方法是学习其他博客的解法
    • 更优解法实现
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      /* 解法二 Manacher Algorithm 马拉车算法 */

      class Solution {
      public:
          string longestPalindrome(string s) {
              string str = "$#";
              for(int i = 0; i < s.size(); ++i) 
                  str = str + s[i] + "#";
              int maxLen = -1;    // 最长回文子串的长度
              int maxId = -1;	    // 最长回文子串中心点的位置
              int p[str.size()] = {}; // 记录当前为起点回文串的长度
              int id = 0, mx = 0; // id为已知的最大回文子串中心的位置，mx是已知最大回文串的右边界

              for(int i = 1; i < str.size(); ++i) {
                  if(i < mx)
                      p[i] = min(p[2 * id - i], mx - i);
                  else 
                      p[i] = 1;

                  while(str[i - p[i]] == str[i + p[i]])
                      p[i]++;

                  // 我们每走一步i，都要和mx比较，我们希望mx尽可能的远，这样才能更有机会执行if (i < mx)这句代码，从而提高效率
                  if(mx < i + p[i]) {
                      id = i;
                      mx = i + p[i];
                  }

                  if(p[i] - 1 > maxLen) {
                      maxLen = p[i] -1;
                      maxId = i;
                  } 			
              }

              int start = (maxId - maxLen - 1) / 2; // 将最长回文子串起始位置转换回原串
              return s.substr(start, maxLen);
          }

      };