經典題目
-
- 5. 最長回文子串（多種解法）
- 131. 分割回文串（dfs）
- 132. 分割回文串 II（動态規劃）
- 214. 最短回文串（KMP）
5. 最長回文子串（多種解法）
leetcode 5
給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
思路：
- 反轉字元串得到s’，求s和s’的最長公共子串，并判斷該子串是否對應s和s’的同一位置。時間複雜度 O ( n 2 ) O(n^2) O(n2)，空間複雜度 O ( n 2 ) O(n^2) O(n2)。
- 動态規劃。維護一個二維數組 dp[i][j] 表示 s[i] 到 s[j] 是否為回文子串，易知狀态轉移方程為 dp[i][j] = dp[i+1][j-1]&&s[i]==s[j]。時間複雜度 O ( n 2 ) O(n^2) O(n2)，空間複雜度 O ( n 2 ) O(n^2) O(n2)。
- 中心擴充法。根據回文串長度的奇偶性分兩種情況判斷，isPalindrome(s, i, i)和isPalindrome(s, i, i+1)，分别用來搜尋以 s[i] 為中心和以 s[i] s[i+1] 為中心的最長回文子串。時間複雜度 O ( n 2 ) O(n^2) O(n2)，空間複雜度 O ( 1 ) O(1) O(1)。
- Manacher算法
反轉字元串
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if(n < 2) return s;
// 反轉s
string rev_s = "";
for(int i = n - 1; i >= 0; i--) rev_s += s[i];
// 聲明dp數組，n+1維是因為狀态轉移方程裡有[i-1][j-1]
int dp[n+1][n+1];
memset(dp, 0, sizeof(dp));
// 填dp數組
int maxx = 0, end = 0; // maxx是最長回文子串長度，end是對應的s中的index
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(s[i - 1] == rev_s[j - 1]) dp[i][j] = dp[i-1][j-1] + 1;
if(dp[i][j] > maxx && n - j + dp[i][j] == i) { // n - j + dp[i][j]是将s'中第j位的字元傳回到s中對應的index
maxx = dp[i][j];
end = i - 1;
}
}
}
return s.substr(end - maxx + 1, maxx);
}
};
動态規劃
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if(n < 2) return s;
// 聲明dp數組,做了空間複雜度優化，原始dp[i][j]表示從s[i]到s[j]是否為回文子串
int dp[n];
memset(dp, 0, sizeof(dp));
int maxx = 1, end = 0;
for(int i = n - 1; i >= 0; i--) { // 從後往前周遊（因為需要dp[i+1][j-1]）
for(int j = n - 1; j >= i; j--) { // 從後往前周遊（因為需要dp[i+1][j-1]）
if(i == j) dp[j] = 1;
else if(i + 1 == j) {
dp[j] = (s[i] == s[j]);
if(dp[j] == 1 && maxx < 2) {
maxx = 2;
end = j;
}
}
else {
dp[j] = dp[j-1] && (s[i] == s[j]);
if(dp[j] == 1 && j - i + 1 > maxx) {
maxx = j - i + 1;
end = j;
}
}
}
}
return s.substr(end - maxx + 1, maxx);
}
};
中心擴充法
class Solution {
public:
int maxx = 0;
int l_max = 0;
void findLongest(string&s, int l, int r) {
int n = s.size();
while(l >= 0 && r < n && s[l] == s[r]) {
l--;
r++;
}
if(r - l - 1 > maxx) {
maxx = r - l - 1;
l_max = l + 1;
}
}
string longestPalindrome(string s) {
int n = s.size();
if(n < 2) return s;
for(int i = 0; i < n; i++) {
findLongest(s, i, i);
findLongest(s, i, i + 1);
}
return s.substr(s, l_max, maxx);
}
};
Manacher算法
class Solution {
public:
string longestPalindrome(string s) {
}
};
131. 分割回文串（dfs）
leetcode 131
給定一個字元串 s，将 s 分割成一些子串，使每個子串都是回文串。
傳回 s 所有可能的分割方案。
思路： 題目要求所有可能的分割方案，是以想到使用dfs暴力搜尋。
注意： 搜尋的範圍（for循環）是目前的左邊界可能對應的回文右邊界。
class Solution {
public:
vector<vector<string>> ans;
// 判斷是否是回文串
bool isValid(string& s, int l, int i) {
while(l < i) {
if(s[l++] != s[i--]) return false;
}
return true;
}
// dfs搜尋
void dfs(string& s, vector<string>& vec, int l) {
int n = s.size();
if(l > n - 1) { // 如果左區間溢出右邊界，傳回
ans.push_back(vec);
return;
}
for(int i = l; i < n; i++) { // 從目前左邊界l搜尋可能的回文右邊界i
if(!isValid(s, l, i)) continue;
vec.push_back(s.substr(l, i - l + 1));
dfs(s, vec, i + 1);
vec.pop_back(); // 回退
}
}
vector<vector<string>> partition(string s) {
int n = s.size();
if(n == 0) return ans;
vector<string> vec;
dfs(s, vec, 0);
return ans;
}
};
132. 分割回文串 II（動态規劃）
leetcode 132
給定一個字元串 s，将 s 分割成一些子串，使每個子串都是回文串。
傳回符合要求的最少分割次數。
思路： 因為求的是最值（最小分割次數），并且可以将問題劃分為最優子問題，是以考慮使用動态規劃來做。
注意： 因為之後要用min比較得到最小分割次數，是以初始化的時候将dp數組初始為目前可能的最大分割次數。
class Solution {
public:
// 判斷是否是回文
bool isValid(string&s, int l, int r) {
while(l < r) {
if(s[l++] != s[r--]) return false;
}
return true;
}
int minCut(string s) {
int n = s.size();
if(n < 2) return 0;
int dp[n];
for(int i = 0; i < n; i++) dp[i] = i; // 初始化為最大分割次數
for(int i = 0; i < n; i++) {
if(isValid(s, 0, i)) dp[i] = 0; // 如果整個都是個回文串，dp[i]當然等于0
else {
for(int j = 1; j <= i; j++) { // 周遊以目前位置結尾的回文串
if(isValid(s, j, i)) {
dp[i] = min(dp[i], dp[j-1] + 1); // 尋找最小分割次數的組合
}
}
}
}
return dp[n-1];
}
};
214. 最短回文串（KMP）
leetcode 214
給定一個字元串 s，你可以通過在字元串前面添加字元将其轉換為回文串。找到并傳回可以用這種方式轉換的最短回文串。
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)