1中心扩散

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:
    void help(const string &s, int left, int right, int& start, int& maxlen){    //中心扩散
        while(left >= 0 && right < s.size())
        {
            if(s[left] != s[right]) break; 
            --left;
            ++right;           
        }                         
        if(right - left - 1 > maxlen )   //退出循环时，串的区间实际上是[left+1,right-1]
        {                                //区间长度，为(right - 1) - (left + 1) + 1 =  right -left - 1
            start = left + 1;
            maxlen = right -left - 1;
        }      
    }
    string longestPalindrome(string s) {
        int start = 0, maxlen = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            help(s,i,i,start,maxlen);        
            help(s,i,i+1,start,maxlen);
        }
        return s.substr(start,maxlen);
    }

};

2动态规划

dp[i][j] 表示对应 i 到 j 的区间是否是回文串

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
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() < 2)    return s;
        int start = 0, maxlen = 1, n = s.size();
        vector<vector<int>> dp (n,vector<int>(n));
        for(int i = 0; i < n; ++i)
            dp[i][i] = true;        //对角线均为true,因为一个元素肯定是回文子串
        for(int j = 1; j < n; ++j)
        {
            for(int i = 0; i < j; ++i)
            {
                if(s[i] != s[j])    dp[i][j] = false;
                else
                {
                    if((j-1) - (i+1) + 1 < 2)   dp[i][j] = true;    //如果内部区间长度小于等于1
                    else
                    {
                        if(dp[i+1][j-1])    dp[i][j] = true;        //看内部区间是否是回文
                    }
                }

                if(dp[i][j] && j - i + 1 > maxlen)  
                {
                    start = i;
                    maxlen = j - i + 1;  
                }  
            }
        }

        return s.substr(start,maxlen);
    }
};