Longest Palindromic Substring 最长回文子字符串

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Difficulty:Medium

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

这道题参考Grandyang,他博客里有全套leetcode讲解.

求最长回文串,回文串就是正着读反着读都一样的字符串.下面的解法是以一个字符为中心向两边扩散并比较

解法1: O(n^2)

class Solution {
public:
    public:
    string longestPalindrome(string s) {
        int startIdx = 0, left = 0, right = 0, len = 0;
        for (int i = 0; i < s.size() - 1; ++i) {
            if (s[i] == s[i + 1])
            {
                left = i;
                right = i+1;
                searchPalindrome(s, left, right, startIdx, len);
            }
            left = right = i;
            searchPalindrome(s, left, right, startIdx, len);
        }
        if (len==0)
            len = s.size();
        return s.substr(startIdx,len);
    }
private:
    void searchPalindrome(string s,int left,int right,int& startIdx,int& len)
    {
        int step = 1;
        while ((left-step)>=0&&(right+step)<s.size())
        {
            if (s[left-step]!=s[right+step])
                break;
            ++step;
        }
        int wide = right-left+2*step-1;
        if (len < wide)
        {
            len = wide;
            startIdx = left-step+1;
        }
    }
};

解法2

下面用动态规划来解,我们需要维护一个二维数组dp,其中dp[i][j]表示字符区间[i,j]是否为回文串,当i=j时,只有一个字符串,可定为回文串,如果i=j+1,说明是相邻字符,此时需要判断s[i]是否等于s[j],如果i和j不相邻,即i-j>=2时,除了判断s[i]和s[j]相等之外,dp[j+1][i-1]若为真,就是回文串.

class Solution {
public:
    public:
    string longestPalindrome(string s) {
        int size = s.size();
        //int dp[size][size]={0}编译不过的话试试int dp[size][size]; dp[size][size]={0};
        int dp[size][size]={0},left=0,right=0,len=0;
        for (int i=0;i<size;i++)
        {
            for (int j=0; j<i; j++) {
                dp[j][i] = (s[i]==s[j] && (i-j<2||dp[j+1][i-1]));
                if (dp[j][i] && len<i-j+1) {
                    len=i-j+1;
                    left=j;
                    right=i;
                }
            }
            dp[i][i] = 1;
        }
        return s.substr(left,right-left+1);
    }
};

解法3 O(n) 马拉车Manacher

运用马拉车算法Manacher(专门解决回文子串的算法),这种算法可以使时间复杂度提升到O(n)

class Solution {
public:
    string longestPalindrome(string s) {
        string t ="$#";
        for (int i = 0; i < s.size(); ++i) {
            t += s[i];
            t += '#';
        }
        int p[t.size()] = {0}, id = 0, mx = 0, resId = 0, resMx = 0;
        for (int i = 0; i < t.size(); ++i) {
            p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
            while (t[i + p[i]] == t[i - p[i]]) ++p[i];
            if (mx < i + p[i]) {
                mx = i + p[i];
                id = i;
            }
            if (resMx < p[i]) {
                resMx = p[i];
                resId = i;
            }
        }
        return s.substr((resId - resMx) / 2, resMx - 1);
    }
};
 
comments powered by Disqus