文章目录
- 回文子串
- 最长回文子串
- 分割回文串 IV
- 分割回文串 II
- 最长回文子序列
- 让字符串成为回文串的最少插入次数
回文子串
题目：回文子串
思路
- 状态表示：
dp[i][j]表示s字符串由i到j是否是回文子串 - 状态转移方程：
s[i] != s[j]，则i到j一定不是回文串；s[i] == s[j]- 当
i == j时，即只有一个字符，则一定是回文串，dp[i][j] = true - 当
i + 1== j时，即有两个字符，则一定是回文串，dp[i][j] = true - 否则，说明
i到j中间还有其他的字符，此时如果i + 1到j - 1是回文串，也就说明i到·j是回文串，所以dp[i][j] = dp[i + 1][j - 1]
- 当
- 初始化：此题不用初始化
- 填表顺序：由
dp[i][j] = dp[i + 1][j - 1]，知i + 1一定要在i前计算，所以从下往上填表； - 返回值：返回
dp表中为true的个数
C++代码
class Solution
{
public:
int countSubstrings(string s)
{
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n));
int ret = 0;
for(int i = n - 1; i >= 0; i--)
{
for(int j = i; j < n; j++)
{
if(s[i] == s[j])
{
dp[i][j] = (i == j || j == i + 1) ? true : dp[i + 1][j - 1];
}
if(dp[i][j]) ret++;
}
}
return ret;
}
};
最长回文子串
题目：最长回文子串
思路
此题和上题基本一致，只需在每次碰到
true时，判断当前回文子串的长度是否为大，如果是，则更新其起始下标以及长度；
C++代码
class Solution
{
public:
string longestPalindrome(string s)
{
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n));
int start = 0, len = 0;
for(int i = n - 1; i >= 0; i--)
{
for(int j = i; j < n; j++)
{
if(s[i] == s[j])
{
dp[i][j] = (i == j || j == i + 1) ? true : dp[i + 1][j - 1];
}
if(dp[i][j] && j - i + 1 > len)
start = i, len = j - i + 1;
}
}
return s.substr(start, len);
}
};
分割回文串 IV
题目：分割回文串 IV
思路
依照第一题的解法将所有的子串都进行统计，遍历计算每个分割位置组成的3个子串是否都符合回文子串即可。
C++代码
class Solution
{
public:
bool checkPartitioning(string s)
{
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n));
for(int i = n - 1; i >= 0; i--)
{
for(int j = i; j < n ; j++)
{
if(s[i] == s[j])
{
dp[i][j] = (i == j || j == i + 1) ? true : dp[i + 1][j - 1];
}
}
}
for(int i = 1; i < n - 1; i++)
{
for(int j = i; j < n - 1; j++)
{
if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])
return true;
}
}
return false;
}
};
分割回文串 II
题目：添加链接描述
思路
- 状态表示：
dp[i]表示，字符串s从[0, i]区间上的最长的子串，最少分割次数 - 状态转移方程：
[0 - i]是回文串：0[0 - i]不是回文串（0 < j <= i），[j, i]是否回文：- 是，
dp[j - 1] + 1 - 不是，
min(dp[j - 1] + 1, dp[i]
- 是，
- 优化：用一个
dp表快速判断字符串中的子串是否回 - 初始化：防止在求
min时，0干扰结果，初始化为无穷大 - 填表顺序： 从左往右
- 返回值：
dp[n - 1]
C++代码
class Solution
{
public:
int minCut(string s)
{
int n = s.size();
vector<vector<bool>> isPal(n, vector<bool>(n));
for(int i = n - 1; i >= 0; i--)
for(int j = i; j < n; j++)
if(s[i] == s[j])
isPal[i][j] = (i == j || j == i + 1) ? true : isPal[i + 1][j - 1];
vector<int> dp(n, INT_MAX);
for(int i = 0; i < n; i++)
{
if(isPal[0][i]) dp[i] = 0;
else
{
for(int j = 1; j <= i; j++)
if(isPal[j][i])
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
return dp[n - 1];
}
};
最长回文子序列
题目：最长回文子序列
思路
- 状态表示：
dp[i][j]表示字符串s中[i, j]区间内的所有子序列中，最长的回文子序列的长度 - 状态转移方程：
s[i] == s[j]i == j：dp[i][j] = 1i + 1 == j：dp[i][j] = 2i + 1 < j：dp[i][j] = dp[i + 1][j - 1] + 2
s[i] != s[j]：dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
- 初始化：特殊位置，状态转移方程已经考虑过了，不用初始化
- 填表顺序：计算
dp[i][j]时，需要用到dp[i + 1][j]，所以从下往上，从左往右填 - 返回值：
dp[0][n - 1]
C++代码
class Solution
{
public:
int longestPalindromeSubseq(string s)
{
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
for(int i = n - 1; i >= 0; i--)
for(int j = i; j < n; j++)
{
if(s[i] == s[j])
{
if(i == j) dp[i][j] = 1;
else if(i + 1 == j) dp[i][j] = 2;
else dp[i][j] = dp[i + 1][j - 1] + 2;
}
else
{
dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
}
}
return dp[0][n - 1];
}
};
让字符串成为回文串的最少插入次数
题目：让字符串成为回文串的最少插入次数
思路
-
状态表示：
dp[i][j]表示字符串s中[i, j]区间内的子串，让字符串成为回文串的最少插入次数 -
状态转移方程：
s[i] == s[j]i == j：dp[i][j] = 0i + 1 == j：dp[i][j] = 0i + 1 < j：dp[i][j] = dp[i + 1][j - 1]
s[i] != s[j]：- 在
i位置的左边，即下标为i - 1位置添加一个s[j]，此时只要保证[i, j - 1]成为回文串即可 ，dp[i][j] = dp[i][j - 1] + 1 - 在
j位置的右边，即下标为j + 1位置添加一个s[i]，此时只要保证[i + 1, j]成为回文串即可 ，dp[i][j] = dp[i + 1][j] + 1 - 综上，
dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]) + 1
- 在
-
初始化：特殊位置，状态转移方程已经考虑过了，不用初始化
-
填表顺序：计算
dp[i][j]时，需要用到[i + 1]和[j - 1]，所以从下往上，从左往右填 -
返回值：
dp[0][n - 1]
C++代码
class Solution
{
public:
int minInsertions(string s)
{
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
for (int i = n - 1; i >= 0; i--)
for (int j = i + 1; j < n; j++)
{
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1];
else
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
}
return dp[0][n - 1];
}
};
