5. 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.

找出给定数组中，最长的回文子串。最长输入尾1000。

样例

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Example 3:

Input: "abcd"
Output: "a"

Example 4:

Input: "eeeeeeeeeeeeeeeeeeeeee"
Output: "eeeeeeeeeeeeeeeeeeeeee"

思路1：暴力，不可行。

判断每一个字串是否是回文串，找出最长。

事件复杂度：O(n3)   (1000的输入， n3复杂度， 10003=109，会超1000ms）

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         string res = "";
 5         int len = s.length();
 6         if(len == 0 || len == 1)
 7             return s;
 8 
 9         for(int i=0; i<len; i++)
10         {
11             string tmpStr = "";
12             tmpStr += s[i];
13             int j = i+1;
14             for(; j<len; j++)
15             {
16                 if(s[j] != s[i])
17                     tmpStr += s[j];
18                 else
19                 {
20                     tmpStr += s[j];
21                     if(judge(tmpStr) && tmpStr.length() > res.length())
22                         res = tmpStr;
23                 }
24             }
25         }
26         if(res.length() == 0)
27             res += s[0];
28         return res;
29     }
30     
31     bool judge(string s)
32     {
33         int len = s.length();
34         for(int k=0; k<=len/2; k++)
35             if(s[k] != s[len-1-k])
36                 return false;
37         return true;
38     }
39 };

 

思路2：DP

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