回文子串
https://leetcode.cn/problems/palindromic-substrings
我们可以使用二维的 dp 表记录所有的子串情况，dp[i][j] 表示 以 i 起始，j 结尾的子串是否是回文串
状态转移方程推导：回文串要求开头和结尾的两个元素必须是相同的，即当 s[i] == s[j] 的时候，才有机会成为回文串，然后如果 i == j 那说明这是一个字符，一个字符可以构成回文串，赋值 true，如果 i + 1 == j 说明是两个相邻的字符，也是回文串赋值为true，最后就是 i + 1 < j 的时候，我们还要判断 i+1 到 j-1 是不是回文串，是的话整个字符串都是回文串，不是的话整个子串都不是回文串，即 dp[i][j] = dp[i+1][j-1]
填表顺序，由于需要用到 dp[i+1][j-1] 的数值，需要从下到上填表
class Solution {
public int countSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int ret = 0;
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 || i + 1 == j) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i+1][j-1];
}
}
if(dp[i][j]) {
ret++;
}
}
}
return ret;
}
}
最长回文子串
https://leetcode.cn/problems/longest-palindromic-substring
dp[i][j] 表示 i 起始，j 结束的回文子串最大长度，如果不是回文串那么长度为 0
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
int[][] dp = new int[n][n];
int len = 0;
int start = 0;
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] = 1;
} else if(i + 1 == j) {
dp[i][j] = 2;
} else if(dp[i+1][j-1] != 0) {
dp[i][j] = dp[i+1][j-1] + 2;
}
}
if(len < dp[i][j]) {
len = dp[i][j];
start = i;
}
}
}
return s.substring(start, start + len);
}
}
分割回文串 Ⅳ
https://leetcode.cn/problems/palindrome-partitioning-iv
我们可以使用 boolean 类型的 dp 表保存所有子串是否是回文串的信息
题目要求该字符串能否被划分为三个子串，我们可以利用二层循环，0 ~ i 为第一个字符串，i +1 ~ j 为第二个字符串，j + 1 ~ n - 1为第三个字符串，即 dp[0][i] && dp[i+1][j] && dp[j+1][n-1] 为 true 的时候直接返回 true
class Solution {
public boolean checkPartitioning(String s) {
int n = s.length();
boolean[][] dp = new boolean[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 || 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+1; j < n-1; j++) {
if(dp[0][i] && dp[i+1][j] && dp[j+1][n-1]) {
return true;
}
}
}
return false;
}
}
分割回文串 Ⅱ
https://leetcode.cn/problems/palindrome-partitioning-ii
我们先通过 boolean[][] dp 来 获取字符串所有子串是否为回文串的信息
接着我们再定义一个状态表 f，f[i] 表示 0 ~ i 这个字符串最少分割次数
填表过程中要同时使用两张表的信息，当 dp[0][i] == true，说明 0 - i 这个字符串本身就是一个回文串，不需要分割，赋值为 0
如果 dp[0][i] 不是 true，那么我们要通过第二层 j 循环来判断，如果 dp[j+1][i] = true 的话，我们要看 0 - j 这个字符串最少分割次数，再 j 循环中取最小值。
class Solution {
public int minCut(String s) {
int n = s.length();
boolean[][] dp = new boolean[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 || i + 1 == j) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i+1][j-1];
}
}
}
}
int[] f = new int[n];
for(int i = 0; i < n; i++) {
if(dp[0][i]) {
f[i] = 0;
} else {
for(int j = i - 1; j >= 0; j--) {
if(dp[j+1][i]) {
f[i] = f[i] == 0 ? f[j] + 1 : Math.min(f[i], f[j] + 1);
}
}
}
}
return f[n-1];
}
}
最长回文子序列
https://leetcode.cn/problems/longest-palindromic-subsequence
dp[i][j] 表示 i 到 j 这个字符串的最长回文子序列的长度
当 s[i] == s[j] 的时候，三种情况，第一种 i == j 【就是一个字符】，赋值为 1， 第二种 i + 1 == j 【相邻两个字符】,赋值为2，第三种 i + 1 < j ，说明 i 和 j 之间还要字符串，dp[i][j] = dp[i+1][j-1] + 2
如果 s[i] != s[j] 的话，需要分情况讨论，子序列包含 j 所对应的字符，则 dp[i][j] = dp[i+1][j] ，第二种就是 子序列不包含 j 所对应的字符，dp[i][j] = dp[i][j-1]，二者取最大值即可
返回 dp[0][n-1]，表示 0 ~ n-1 的字符串的最长子序列的长度即为题目要求。
class Solution {
public int longestPalindromeSubseq(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 || i + 1 == j) {
dp[i][j] = j - i + 1;
} else {
dp[i][j] = dp[i+1][j-1] + 2;
}
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
}
让字符串成为回文串的最少插入次数
https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome
dp[i][j] 表示 i 到 j 这个字符串成为回文子串的最少插入次数
当 s[i] == s[j] 的时候，i == j 或者 i+ 1 == j 的话，说明这个字符串本身就是回文串，不需要插入字符，所以 dp[i][j] = 0，当 i + 1 < j 的时候，我们要查看 i + 1 到 j - 1 这个字符串最少插入次数，即 dp[i][j] = dp[i+1][j-1]
如果 s[i] != s[j] 的话，第一种就是插入 s[i] ，dp[i][j] = 1 + dp[i+1][j]
第二种就是插入 s[j]，dp[i][j] = 1 + dp[i][j-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 || 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];
}
}
