文章目录
- 1. 回文子串（647）
- 2. 最长回文子串（5）
- 3. 分割回文串 IV（1745）
- 4. 分割回文串 II（132）
- 5. 最长回文子序列（516）
- 6. 让字符串成为回文串的最少插入次数（1312）
1. 回文子串（647）
题目描述：
状态表示：
设置一个布尔类型二维数组dp，使用dp[i][j]来表示在i和j这个闭区间内的子串是否为回文子串。
状态转移方程：
当i和j位置的元素相同时分为三种情况，第一种是i等于j，第二种就是i+1等于j，第三种是就是除了i和j位置的元素还包含中间很多元素，那么dp[i][j]=dp[i+1][j-1]。
初始化：
这里无需初始化，都赋为false即可。
填表顺序：
填表要使用到两层循环，从左至右，从上到下。
返回值：
返回值就是返回dp数组中为true的个数。
代码如下：
class Solution {
public int countSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int ret = 0;
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j)) {
if (i == j) {
dp[i][j] = true;
} else if (i + 1 == j) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
if (dp[i][j]) {
ret++;
}
}
}
}
return ret;
}
}
题目链接
时间复杂度:O(N^2)
空间复杂度:O(N^2)
2. 最长回文子串（5）
题目描述：
状态表示：
这题状态表示和上一题一致。
状态转移方程：
这题状态转移方程和上一题也是一致的。
初始化：
初始化就是全是false，即不用初始化。
填表顺序：
从左至右，从上到下。
返回值：
返回dp数组中值为true的元素的i和j坐标差值为最大值的子串。
代码如下：
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int startIndex = 0;
int endIndex = 0;
int max = Integer.MIN_VALUE;
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j)) {
if (i == j) {
dp[i][j] = true;
} else if (i + 1 == j) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && j - i + 1 > max) {
max = j - i + 1;
startIndex = i;
endIndex = j;
}
}
}
return s.substring(startIndex, endIndex + 1);
}
}
题目链接
时间复杂度:O(N^2)
空间复杂度:O(N^2)
3. 分割回文串 IV（1745）
题目描述：
状态表示：
这题的状态表示与前两题一致。
状态转移方程：
与前两题一致。
初始化：
与前两题一致。
填表顺序：
与前两题一致。
返回值：
这题的返回值有点特殊，需要使用两层循环，将两层循环的下标用来分割字符串s并且判断分割好的三个子串在dp表中的值是否为true，如果都为true最终返回就是true，如果遍历完成没有一次是true，那么就返回false。
代码如下：
class Solution {
public boolean checkPartitioning(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j)) {
if (i == j) {
dp[i][j] = true;
} else if (i + 1 == j) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
}
}
for (int i = 0; i < n - 1; i++) {
for (int j = i; j < n - 1; j++) {
if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1]) {
return true;
}
}
}
return false;
}
}
题目链接
时间复杂度:O(N^2)
空间复杂度:O(N^2)
4. 分割回文串 II（132）
题目描述：
状态表示：
这里有两个动态数组，第一个sup二维数组用于辅助运算，思想和前面几题类似，就是判断i到j位置是否为一个回文子串。第二个一维的动态数组dp，dp[i]表示以i位置元素为结尾的子串可以被分割为多个回文子串的最小次数。
状态转移方程：
对于二位数组的状态转移方程我们不多赘述，前面几题用很多。对于一维数组的dp[i]，如果0~i是一个回文子串，那么dp[i]的值就是0，另一种情况就是0到i不是一个回文子串，那么我们固定住i，利用一个循环来遍历i前面的元素使用j来表示，如果j到i是一个回文子串，那么更新dp[i]=Math.min(dp[i],dp[j-1]+1)。
初始化：
为了不影响运算，将dp数组全初始化为最大值。
填表顺序：
dp数组从左至右。
返回值：
因为要返回整个字符串的最小分割次数，所以直接返回dp[n-1]即可。
代码如下：
class Solution {
public int minCut(String s) {
int n = s.length();
boolean[][] sup = new boolean[n][n];
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j)) {
if (i == j) {
sup[i][j] = true;
} else if (i + 1 == j) {
sup[i][j] = true;
} else {
sup[i][j] = sup[i + 1][j - 1];
}
}
}
}
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < n; i++) {
if (sup[0][i]) {
dp[i] = 0;
} else {
for (int j = i; j >= 1; j--) {
if (sup[j][i]) {
dp[i] = Math.min(dp[i], dp[j - 1] + 1);
}
}
}
}
return dp[n - 1];
}
}
题目链接
时间复杂度:O(N^2)
空间复杂度:O(N^2)
5. 最长回文子序列（516）
题目描述：
状态表示：
和第二题一致。
状态转移方程：
和第二题一致。
初始化：
和第二题一致。
填表顺序：
和第二题一致。
返回值：
这题和第二题就是一样的题目，只不过第二题要返回字符串，但是这里返回的只是长度。
代码如下：
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int max = 1;
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j)) {
if (i == j) {
dp[i][j] = true;
} else if (i + 1 == j) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && j - i + 1 > max) {
max = j - i + 1;
}
}
}
return max;
}
}
题目链接
时间复杂度:O(N^2)
空间复杂度:O(N^2)
6. 让字符串成为回文串的最少插入次数（1312）
题目描述：
状态表示：
使用二位数组dp[i][j]表示在i和j区间的子串变成回文子串的最小插入次数。
状态转移方程：
分为两种情况，第一种i和j位置元素相等时，当i+1等于j时，dp[i][j]=0，当i等于j时，dp[i][j]=0，当i+1<j时,dp[i][j]=dp[i+1][j-1]。第二种情况当i和j位置元素不相等时，需要插入元素所以dp[i][j]=Math.min(dp[i+1][j],dp[i][j-1])+1;
初始化：
无需初始化。
填表顺序：
从下到上，从左至右。
返回值：
返回0到n-1的原字符串的最小分割次数即dp[0][n-1]。
代码如下：
class Solution {
public int minInsertions(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
if (i == j) {
dp[i][j] = 0;
} else if (i + 1 == j) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
} else {
dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[0][n - 1];
}
}
题目链接
时间复杂度:O(N^2)
空间复杂度:O(N^2)