133 lines
3.7 KiB
C++
133 lines
3.7 KiB
C++
#include "s0005_longest_palindromic_substring.hpp"
|
||
|
||
// 思路一：字符串翻转 + 动态规划
|
||
// 看到回文串就要想到字符串翻转。
|
||
// 字符串翻转之后问题就可以描述成找到 s 和 reverse(s) 的最长公共子字符串
|
||
// 再看一个例子，S="abc435cba"，S="abc534cba"，最长公共子串是 "abc" 和
|
||
// "cba"，但很明显这两个字符串都不是回文串。
|
||
// 所以我们求出最长公共子串后，并不一定是回文串，我们还需要判断该字符串倒置前的下标和当前的字符串下标是不是匹配。
|
||
|
||
// 思路二：直接动态规划
|
||
// dp[i][j] 表示起始为 i ，终点为 j 的子字符串是否为回文字符串
|
||
// 那么有：
|
||
// if s[i] == s[j]:
|
||
// dp[i][j] = dp[i - 1][j - 1]
|
||
// else:
|
||
// dp[i][j] = false
|
||
// 把 dp 这张二维数组的表全部填好，然后在里面找最长的子字符串。
|
||
// 时间复杂度：O(n^2) 因为总共有 n^2 个状态，计算每个状态需要的时间为 O(1)
|
||
// 空间复杂度：O(n^2) 因为总共需要存储 n^2 个状态。
|
||
string S0005::longestPalindrome1(string s) {
|
||
int len = s.length();
|
||
vector<vector<int>> dp(len, vector<int>(len));
|
||
|
||
if (len < 2) {
|
||
return s;
|
||
}
|
||
|
||
// L 表示子字符串长度
|
||
// L = 1, true
|
||
for (int i = 0; i < len; i++) {
|
||
dp[i][i] = true;
|
||
}
|
||
|
||
// L = 2
|
||
// if l == r, dp = true
|
||
// else, dp = false
|
||
for (int i = 0; i < len - 1; i++) {
|
||
if (s[i] == s[i + 1]) {
|
||
dp[i][i + 1] = true;
|
||
} else {
|
||
dp[i][i + 1] = false;
|
||
}
|
||
}
|
||
|
||
// L >= 3
|
||
// if l == r, dp = dp_prev
|
||
// else, dp = false
|
||
for (int L = 3; L <= len; L++) {
|
||
for (int i = 0; i + L - 1 < len; i++) {
|
||
if (s[i] == s[i + L - 1]) {
|
||
dp[i][i + L - 1] = dp[i + 1][i + L - 2];
|
||
} else {
|
||
dp[i][i + L - 1] = false;
|
||
}
|
||
}
|
||
}
|
||
|
||
// find max len
|
||
int maxLen = 1;
|
||
int beginIndex = 0;
|
||
for (int i = 0; i < len; i++) {
|
||
for (int j = i; j < len; j++) {
|
||
if (dp[i][j]) {
|
||
if (j - i + 1 > maxLen) {
|
||
maxLen = j - i + 1;
|
||
beginIndex = i;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
return s.substr(beginIndex, maxLen);
|
||
}
|
||
|
||
// 思路三：中心扩散算法
|
||
// 每个回文字符串都有一个“回文中心”
|
||
// 这个回文中心要么是一个长度为 1 的字符，要么是一个长度为 2
|
||
// 的字符串（这个字符串的两个字符都相等）
|
||
// “回文中心”实际上是两种边界情况，也就是说每个可能的结果都是由边界情况扩展开来的
|
||
// 因此我们可以遍历每个边界情况，对它进行扩展
|
||
|
||
// 输入为字符串和边界情况的那一点
|
||
// 返回值包含为扩展的结果
|
||
S0005Result S0005::expand(string s, int i) {
|
||
int len = s.length();
|
||
|
||
if (i == len - 1) {
|
||
return S0005Result{i, i, i, i};
|
||
}
|
||
|
||
// 边界情况为长度为 1 的字符时
|
||
int left1 = 0, right1 = 0;
|
||
for (int x = 0; i + x < len && i - x >= 0; x++) {
|
||
if (s[i - x] == s[i + x]) {
|
||
left1 = i - x;
|
||
right1 = i + x;
|
||
} else {
|
||
break;
|
||
}
|
||
}
|
||
|
||
// 边界情况为长度为 2 的字符串时
|
||
int left2 = 0, right2 = 0;
|
||
for (int x = 0; i + x + 1 < len && i - x >= 0; x++) {
|
||
if (s[i - x] == s[i + x + 1]) {
|
||
left2 = i - x;
|
||
right2 = i + x + 1;
|
||
} else {
|
||
break;
|
||
}
|
||
}
|
||
|
||
return S0005Result{left1, right1, left2, right2};
|
||
}
|
||
|
||
string S0005::longestPalindrome2(string s) {
|
||
int len = s.length();
|
||
int left = 0, right = 0;
|
||
S0005Result result{0, 0, 0, 0};
|
||
for (int i = 0; i < len; i++) {
|
||
result = expand(s, i);
|
||
if (result.right1 - result.left1 > right - left) {
|
||
right = result.right1;
|
||
left = result.left1;
|
||
}
|
||
if (result.right2 - result.left2 > right - left) {
|
||
right = result.right2;
|
||
left = result.left2;
|
||
}
|
||
}
|
||
return s.substr(left, right - left + 1);
|
||
}
|