[leetcode] 5 最长回文子串

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

思考：1.动态规划

子串若头尾相同且内部也是回文子串则次子串也是回文子串，内部不是则必定不是。

状态定义

dp[i,j]：字符串s从索引i到j的子串是否是回文串

true： s[i,j] 是回文串
false：s[i,j] 不是回文串

转移方程

    dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
    s[i] == s[j]：说明当前中心可以继续扩张，进而有可能扩大回文串的长度
    dp[i+1][j-1]：true
    说明s[i,j]的**子串s[i+1][j-1]**也是回文串
    说明，i是从最大值开始遍历的，j是从最小值开始遍历的
    特殊情况
     j - i < 2：意即子串是一个长度为0或1的回文串

自己遇到的困难：

看了大神的思路，状态转移方程后无从下手，不知道边界条件与递推遍历的顺序。

注意此处状态方程dp[i+1][j-1]说明了dp[i][j]的状态要依靠dp[i+1][j-1],所以要从i最大处，j最小处开始递推，边界则是两个相等。

AC代码

 1 int dp[1000][1000];
 2 class Solution {
 3 public:
 4     string longestPalindrome(string s) {
 5         for(int i = 0;i < 1000;i++)
 6     {
 7         for(int j = 0;j < 1000;j++)
 8         dp[i][j] = 0;
 9     }
10     for(int i = 0;i < 1000;i++)
11     {
12         dp[i][i] = 1; 
13     } 
14      int len = s.size();
15     int maxlen = 0;
16     int curlen = 0;
17     int start = 0;
18     int i;
19     int j;
20     for( i = len - 1;i >= 0;i--)
21     {
22         for( j = i;j < len;j++)
23         {
24             if(s[i] == s[j])
25             {
26                 if(j - i  < 3)
27                 dp[i][j] = 1;else
28                 dp[i][j] = dp[i + 1][j - 1];
29             }else
30             dp[i][j] = 0;
31             
32             if(dp[i][j] == 1)
33             {
34                 curlen = j - i;
35                 if(curlen > maxlen)
36                 {
37                         maxlen = curlen;
38                         start = i;
39         
40                 }    
41             
42             }
43         }
44     
45     }
46     for(int k = 0;k <= maxlen;k++)
47     {
48         printf("%c",s[start + k]);
49     }
50     string s1;                                        //学习C风格字符串与C++ string区别
51     s1 = s;
52     return s1.substr(start, maxlen + 1);
53     }
54 };

遗留问题

1.此题有更高效的算法思路