leetcode最长回文子串

1.暴力解法

即判断从i--j是否为回文子串，取最长即可

2.动态规划

一个回文子串其左字母和右字母是相同的，设字符串长度为n ,dp[n][n],dp[i][j]表示从i-j是否为回文字符串

若i=j

dp[i][i]=true;//即最短回文子串的长度为1，

对于i不等于j

dp[i][j]=dp[i+1][j-1]&&si==sj,即i--j若为回文字符串，则i+1---j-1也是回文字符串

此处需要注意,

当j=i+1:

dp[i][i+1]=(s[i]==s[i+1]);//因为dp[i][i]一定为true；如***aa**这种情况

当j=i+2:

dp[i][i+2]=(s[i]==s[i+2]);//此处指***aba**这种情况，当然***bbb***也一样

故上述情况可以归纳如下：

当j-i的值<=2时，dp[i][j]的值只取决于s[i]是否等于s[j],

当j-i>2时，dp[i][j]的值由s[i]==s[j]和dp[i+1][j-1]共同决定

if(s[i]==s[j]&&(j-i<=2||dp[i+1][j-1])

   dp[i][j]=true;

由于是dp[i][j]的判断需要借助dp[i+1][j-1]

故i从尾部开始，j从i的下一位到尾部

代码如下：

注：代码中j从i开始是将dp的初始化也放在其中了

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        string res="";
        int l=0;  //l用来记录当前最长的回文子串
        if (s.size()==0) return res;
        if(s.size()==1)return s;
        res=s[0];//返回子串初始化为第一个元素
        vector<vector<bool>> dp(n, vector<bool>(n));
          for (int i = n-1; i>=0; i--) {
            for (int j=i;j<n;j++){
                if((s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1])){
                    dp[i][j]=true;
                    if(j-i>l){
                        res=s.substr(i,j-i+1);//返回某个子串
                        l=j-i;
                    }
                }
            }
        }
        return res;
    }
};

 

时间复杂度O(n*n),空间复杂度O(n*n)

3.中心扩展算法

回文字符串左右为镜像，只需要找到中心，然后向两边扩展即可。

对于长度为n的字符串，其中心为2*n-1(n+n-1)。

1)以某一个字符为中心，有n个,此时回文子串长度为奇数,如***aaabaaa**

2)以两个字符中间为中心，有n-1个，回文字符串长度为偶数，如***aaabbaaa**

两个情况的字符串起始和结束位置如下图:

即可以统一为：

left=i-(len-1)/2;

right=i+len/2;

代码如下：

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
       if(s.empty()|n<1)
         return "";
        int start=0,end=0;
        for(int i=0;i<n;i++)
        {
            int len1=expandcenter(s,i,i);
            int len2=expandcenter(s,i,i+1);
            int len=max(len1,len2);
            if(len>end-start)
            {
                start=i-(len-1)/2;
                end=i+len/2;
            }
        }
        return s.substr(start,end-start+1);//返回从start开始，长度为end-start+1的字符串
    }
    int expandcenter(string s,int left,int right)
    {
        while(left>=0&&right<s.size()&&s[left]==s[right])
        {
            right++;
            left--;
        }
        return right-left-1;
    }
};

 

时间复杂度o(n*n),空间复杂度o(1)

4.Manacher 算法