1、題目描述
給你一個字符串 s，找到 s 中最長的 回文 子串。
示例 1:
輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案。
示例 2:
輸入：s = "cbbd"
輸出："bb"
2、中心擴展法解題
- 解題思路：回文中心的兩側互相對稱。因此，回文可以從他的中心展開，并且只有 2n-1 個這樣的中心（一個元素為中心的情況有 n 個，兩個元素為中心的情況有 n-1 個）
class Solution {
public:int expand(const std::string& s, int l, int r) {while(l >= 0 && r < s.length() && s[l] == s[r]) {--l;++r;}// 這里需要注意邊界問題處理，代碼走到這里時，l、r相比回文串的索引都移動了一位return r - l - 1;
}
std::string longestPalindrome(std::string s) {int len = s.length();int m = 0, index = 0;for (int i = 0; i < len; ++i) {int l1 = expand(s, i, i);int l2 = expand(s, i, i + 1);if(std::max(l2, l1) > m) {index = i - (std::max(l2, l1) - 1) / 2;m = std::max(l2, l1);}}return s.substr(index, m);
}
};
3、Dp解題
- 初始狀態：
1）dp[i][i]=1; //單個字符是回文串
2）dp[i][i+1]=1 if s[i]=s[i+1]; //連續兩個相同字符是回文串
std::string longestPalindrome_dp(std::string s) {int len = s.length();int max = 1, index = 0;std::vector<std::vector<std::uint8_t>> dp = std::vector<std::vector<std::uint8_t>>(len, std::vector<std::uint8_t>(len, 0));for (int i = 0; i < len; ++i) {dp[i][i] = 1;if(i + 1 < len && s[i] == s[i+1]) {dp[i][i+1] = 1;max = 2;index = i;}}for(int i = 3; i <= len; i++) {for(int j = i - 1; j < len; j++) {if(s[j] == s[j - i + 1] && dp[j-i+2][j-1] == 1) {max = i;index = j - i + 1;dp[j-i+1][j]=1;}}}return s.substr(index, max);}
- 總結，一直對這種斜線充填數據的DP不是很理解，通過這道題目悟出來，一般和個數有關的場景使用這種方式初始化數據。可以理解為是那種確定步長時怎么怎么樣，因為這種方式有一個特點，那就是i-j的差值是固定的，也就是說dp[i][j]的含義是[i, j]之間的數據滿足什么樣的條件。
)
