LeetCode 5. Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.method 1: 中心扩散
要求连续子串，枚举奇数和偶数回文，取最长的
pair<int, int> isValid(string s, int i, int j) {
while (i >= 0 && j < s.size() && s[i] == s[j]) {
i--;
j++;
}
return {i + 1, j - 1};
}
string longestPalindrome(string s) {
int start = 0, end = 0;
for (int i = 0; i < s.size(); i++) {
auto [left1, right1] = isValid(s, i, i); // 奇数个回文
auto [left2, right2] = isValid(s, i, i + 1); // 偶数个回文
if (right1 - left1 > end - start) {
start = left1;
end = right1;
}
if (right2 - left2 > end - start) {
start = left2;
end = right2;
}
}
return s.substr(start, end - start + 1); // [start, end]
}method 2: 动态规划
连续子串
dp[i][j]：表示区间范围[i,j]（注意是左闭右闭）的子串是否是回文子串
s[i] != s[j]，则dp[i][j]=falses[i] == s[j]，有三种情况i == j，指向同一个字符，是回文串，则dp[i][j]=truei与j相差1，两个相同的字符，例如aa，也是回文串，则dp[i][j]=truei与j相差大于1，例如cabac，此时s[i]与s[j]相同，看[i,j]是不是回文串，需要看内部，如果[i+1,j-1]是回文，那[i,j]也是
int countSubstrings(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false));
int maxLen = 0;
int pos = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s[i] == s[j]) {
if (j - i <= 1) dp[i][j] = true;
else dp[i][j] = dp[i + 1][j - 1];
}
if (dp[i][j] && j - i + 1 > maxLen) { // [i, j]
maxLen = j - i + 1;
pos = i;
}
}
}
return s.substr(pos, maxLen);
}相当于一个指针i从后往前遍历，另一个指针j从i开始往后遍历，枚举所有以s[i]开始的子串
LeetCode 647. Palindromic Substrings
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = "abcb"
Output: 5
Explanation: Three palindromic strings: "a", "b", "c", "b", "bcb".method 1: 中心扩散
中心是单个字符，会形成奇数回文，如aba
中心是两个字符，会形成偶数回文，如baab
在字符串中用两个指针从中心向两边扩展，如果相同就继续扩展，否则该中心结束
int cnt = 0;
void isValue(string s, int i, int j) {
// 这里用while，如果是回文可以一直扩展下去
while (i >= 0 && j < s.size() && s[i] == s[j]) {
cnt++;
i--; // i往左扩展
j++; // j往右扩展
}
}
int countSubstrings(string s) {
for (int i = 0; i < s.size(); ++i) {
isValue(s, i, i); // 奇数个回文
isValue(s, i, i + 1); // 偶数个回文
}
return cnt;
}method 2: 动态规划
int countSubstrings(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false));
int res = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s[i] == s[j]) {
if (j - i <= 1) dp[i][j] = true;
else dp[i][j] = dp[i + 1][j - 1];
}
if (dp[i][j]) res++; // [i,j]是回文
}
}
return res;
}LeetCode 516. Longest Palindromic Subsequence
Given a string s, find the longest palindromic subsequence’s length in s.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".Example 2:
Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".method: 动态规划
子序列不要求连续
dp[i][j]：s在区间[i,j]的最长回文子序列长度
如果s[i] == s[j]，那么dp[i][j] = dp[i+1][j-1] + 2
如果s[i] != s[j]，说明s[i]和s[j]的同时加入不能增加区间[i,j]的回文长度，考虑分别加入s[i]或s[j]看哪个可以使得回文长度增加
- 加入
s[i]长度为dp[i][j-1]，相当于删掉s[j] - 加入
s[j]长度为dp[i+1][j]，相当于删掉s[i]
所以，dp[i][j] = max(dp[i][j-1], dp[i+1][j])
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) { // j==i已经初始化为1，从前往后更新
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
