leetcode5

一、动态规划做的

 1 string longestPalindrome(string s) {
 2     int size = s.size();
 3     vector<vector<int>> dp(size, vector<int>(size, 0));
 4     for (int i = 0; i < size; ++i)
 5         dp[i][i] = 1;
 6     int start = 0, end = 0;
 7     int longest = 1;
 8     for (int i = size - 2; i >= 0; --i)
 9     {
10         for (int j = i + 1; j < size; ++j)
11         {
12             if (s[i] == s[j])
13             {
14                 if (dp[i + 1][j - 1] == j - i - 1)
15                 {
16                     dp[i][j] = dp[i + 1][j - 1] + 2;
17                     if (j - i + 1 > longest)
18                     {
19                         longest = j - i + 1;
20                         start = i;
21                         end = j;
22                     }
23                 }
24             }
25             else
26                 dp[i][j] = 0;
27         }
28     }
29     return s.substr(start,end-start+1);
30 }

二、中心扩展算法

 1 int expandAroundCenter(string s, int start, int end)
 2 {
 3     while (start >= 0 && end < s.size() && s[start] == s[end])
 4     {
 5         --start;
 6         ++end;
 7     }
 8     return end - start + 1 - 2;　　//-2：上面越界的时候多了长度2
 9 }
10 string longestPalindrome(string s) {
11     int size = s.size();
12     if (size == 0)
13         return "";
14     int start = 0, end = 0;
15     int longest = 0;
16     for (int i = 0; i < size; ++i)
17     {
18         int len1 = expandAroundCenter(s, i, i);
19         int len2 = expandAroundCenter(s, i, i + 1);
20         if (longest < max(len1, len2))
21         {
22             longest = max(len1, len2);
23             start = i - (longest - 1) / 2;　　//这一行和下一行，就是这么用　
24             end = i + longest / 2;
25         }
26     }
27     return s.substr(start, end - start + 1);
28 }