blob: 4ecba2585f42ddd478599536c5c600ea90c19774 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include "leetcode.h"
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() == 0)
return "";
int i = 0, j = 0, n = s.size();
bool p[n][n] = {false};
for (int x = 0; x < n; x++) {
p[x][x] = true;
if (x == n - 1)
break;
p[x][x + 1] = (s[x] == s[x + 1]);
}
for (int i = n - 3; i >= 0; --i)
for (int j = i + 2; j < n; ++j)
p[i][j] = (p[i + 1][j - 1] && s[i] == s[j]);
int max = 0;
string ans = "";
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (p[i][j] == true && j - i + 1 > max) {
max = j - i + 1;
ans = s.substr(i, j - i + 1);
}
return ans;
}
};
int main() {
Solution obj;
string s = "babad";
cout << obj.longestPalindrome(s);
}
|