题目

题解

1.暴力解法 从前往后遍历途中对 以i为中心对称遍历 和 i也有对称数的对称遍历

2.动态规划 一个回文子串 意味着将两端去掉依然是回文子串 所以我们使用两层vector 记录从开始位置到结束位置是否是回文字符

当s[j]==s[i]时 就去看res[i + 1][j - 1] 是否也为true 是则res[i][j] = true;

单个字符或者两个时直接为true   j - i <= 1->res[i][j] = true;

代码

1.

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 class Solution {
 5 public:
 6     string longestPalindrome(string s) {
 7         string result="";
 8         string tem = "";
 9         int left = 0;
10         int right = 0;
11         for (int i = 0; i < s.size(); i++) {
12         //1.中心对称
13             tem = s[i];
14             left = i-1;
15             right = i + 1;
16             while (left>-1&& right<s.size()&&s[left]==s[right])
17             {
18                 tem = s[left]+tem+s[right];
19                 left--;
20                 right++;
21             }
22             if (result.size() < tem.size()) {
23                 result = tem;
24             }
25             if (tem.size()== s.size()) {
26                 return s;
27             }
28 
29             tem = "";
30         //2.双向对称
31             left = i;
32             right = i + 1;
33             while (left > -1 && right < s.size() && s[left] == s[right])
34             {
35                 tem = s[left] + tem + s[right];
36                 left--;
37                 right++;
38             }
39             if (result.size() < tem.size()) {
40                 result = tem;
41             }
42             if (tem.size() == s.size()) {
43                 return s;
44             }
45         }
46         return result;
47     }
48 };
49 
50 int main() {
51     Solution sol;
52     string s = "cbbd";
53     string reslut=sol.longestPalindrome(s);
54     cout << reslut << endl;
55 }

2.

 1 #include<iostream>
 2 #include<vector>
 3 #include<string>
 4 using namespace std;
 5 //vector<vector<string>>(s.size()) = { vector<string>(s.size(),"233") }
 6 class Solution {
 7 public:
 8     string longestPalindrome(string s) {
 9         int maxlenth = 0;
10         int left = 0;
11         int right = 0;
12         //vector<vector<vector<string>>> res(s.size(), vector<vector<string>>(s.size()) );
13         vector<vector<int>> res(s.size(), vector<int>(s.size(),0));
14         for (int i = s.size() - 1; i >= 0; i--) {
15             for (int j = i; j < s.size(); j++) {
16                 if (s[j]==s[i]) {
17                     //j与i相等 即同一个字符 符合回文
18                     if (j - i <= 1) { 
19                         res[i][j] = true;
20                     }
21                     else if (res[i + 1][j - 1]) { 
22                         res[i][j] = true;
23                     }
24                 }
25                 if (res[i][j] && j - i + 1 > maxlenth) {
26                     maxlenth = j - i + 1;
27                     left = i;
28                     right = j;
29                 }
30             }
31 
32         }
33         return s.substr(left, right - left + 1);
34     }
35 };
36 
37 int main() {
38     Solution sol;
39     string s = "cbbd";
40     string reslut=sol.longestPalindrome(s);
41     cout << reslut << endl;
42 }