leetcode-5

题目：

给你一个字符串 s，找到 s 中最长的 回文子串

示例 1：输入：s = "babad"　　输出："bab"　　解释："aba" 同样是符合题意的答案。

示例 2：输入：s = "cbbd"　　  输出："bb"

提示：   1 <= s.length <= 1000　　s 仅由数字和英文字母组成

推导：

代码：

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         int n = s.size();
 5         int maxLen = 1; // 定义最大回文串长度
 6         int begin = 0;
 7         if (n < 2) {
 8             return s;
 9         }
10 
11         // 创建二维数组dp[i][j]
12         vector<vector<int>> dp(n, vector<int>(n));
13 
14         // 首先对对角线上的单个元素形成的回文赋值true
15         for (int i=0; i<n; ++i) {
16             dp[i][i] = true;
17         } 
18 
19         for (int L=2; L<n; ++L) {
20             for (int i=0; i<n; ++i) {
21                 int j = L+i-1; // 起始的 L = 2，所以 j = 2+0-1 = 1，j = L-1+i, 
22                                // 可见 L-1 始终大于0， 因此 j > i
23                 
24                 // 如果右边界越界，则直接结束循环
25                 if (j >= n) {
26                     break;
27                 }
28 
29                 if (s[i] != s[j]) {
30                     dp[i][j] = false; // 如果串的首尾元素不相等，则判断该串 s[i..j] 不是回文串
31                 } else {
32                     if (L < 4){
33                         dp[i][j] = true; // 看笔记，或者博客园
34                     } else {
35                         dp[i][j] = dp[i+1][j-1]; // 看笔记，或者博客园
36                     }
37                 }
38                 if (dp[i][j] == true && L > maxLen) { 
39                     // 这里的比较条件可写为 if dp[i][j]
40                     // 这是因为 dp[i][j] 中仅存放 true/false，dp[i][j] == true 就相当于dp[i][j]
41                     // 后半部分可省略是因为 L 本身是在递增的，而每次循环 maxLen 的最大值总是当前循环的L 
42                     // 因此后面 L 一定比前面的maxLen要大，所以只要出现首尾相等，就说明L更大，因此可以省略
43                     maxLen = L;
44                     begin = i;
45                 }
46             }
47         }
48         return s.substr(begin, maxLen);
49     }
50 };