动态规划算法专题（六）：回文串问题
目录
1、回文子串（"引子题"）
1.1 算法原理
1.2 算法代码
2、最长回文子串
2.1 算法原理
2.2 算法代码
3、分割回文串 IV（hard）
3.1 算法原理
3.2 算法代码
4、分割字符串 II（hard）
4.1 算法原理
4.2 算法代码
5、最长回文子序列
5.1 算法原理
5.2 算法代码
6、让字符串成为回文串的最少插入次数（hard）
6.1 算法原理
6.2 算法代码
1、回文子串（"引子题"）
. - 力扣（LeetCode）
1.1 算法原理
- 状态表示：
dp[i][j]：[i, j]区间内的子串，是否回文(i <= j)
- 状态转移方程：
s[i] == s[j]：
1. i == j --> true
2. i+1==j --> s(i) == s(j) ? true : false
3. s(i) == s(j) --> dp[i+1][j-1]
- 初始化：
无需初始化（状态转移方程的前两种情况已处理特殊的边界情况）
- 建表顺序：
从下往上(根据状态转移方程)
- 返回值：
dp表中有几个true
1.2 算法代码
class Solution {
public int countSubstrings(String ss) {
char[] s = ss.toCharArray();
int n = s.length;
boolean[][] dp = new boolean[n][n];
int ret = 0;
// 填表 --> 从下往上
for(int i = n - 1; i >= 0; i--) {
// j >= i
for(int j = i; j < n; j++) {
if(s[i] == s[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;
}
}2、最长回文子串
. - 力扣（LeetCode）
2.1 算法原理
本题算法原理与题一完全一致，最终返回最长的回文子串即可。
- 状态表示：
dp[i][j]：[i, j]区间内的子串，是否回文(i <= j)
- 状态转移方程：
s[i] == s[j]：
1. i == j --> true
2. i+1==j --> s(i) == s(j) ? true : false
3. s(i) == s(j) --> dp[i+1][j-1]
- 初始化：
无需初始化（状态转移方程的前两种情况已处理特殊的边界情况）
- 建表顺序：
从下往上(根据状态转移方程)
- 返回值：
最长回文子串
2.2 算法代码
class Solution {
public String longestPalindrome(String ss) {
char[] s = ss.toCharArray();
int n = s.length;
boolean[][] dp = new boolean[n][n];
String ret = "";
int begin = 0;
int end = 0;
// 建表 --> 从下往上
for(int i = n - 1; i >= 0; i--) {
for(int j = i; j < n; j++) {// i <= j
if(s[i] == s[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]) {
// 记录最长回文子串的起始和末尾位置
if(j - i + 1 > end - begin + 1) {
begin = i;
end = j;
}
}
}
}
return ss.substring(begin, end + 1);
}
}3、分割回文串 IV（hard）
. - 力扣（LeetCode）
3.1 算法原理
本题算法原理依旧是在题一判断好哪些子串是回文的基础上，分割字符串，判断是否存在三个回文串即可。
- 状态表示：
dp[i][j]：[i, j]区间内的子串，是否回文(i <= j)
- 状态转移方程：
s[i] == s[j]：
1. i == j --> true
2. i+1==j --> s(i) == s(j) ? true : false
3. s(i) == s(j) --> dp[i+1][j-1]
- 初始化：
无需初始化（状态转移方程的前两种情况已处理特殊的边界情况）
- 建表顺序：
从下往上(根据状态转移方程)
- 返回值：
是否存在三个回文串。
3.2 算法代码
class Solution {
public boolean checkPartitioning(String ss) {
char[] s = ss.toCharArray();
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[i] == s[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];
}
}
}
// 从 i,j 位置 分割字符串
for(int i = 1; i < n; 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;
}
}4、分割字符串 II（hard）
. - 力扣（LeetCode）
4.1 算法原理
本题仍然在题一中 通过二维dp保存所有子串的是否回文的信息 的基础上解题。
- 状态表示：
dp[i]：以[0, i]区间内的子串，最少的分割次数
- 状态转移方程：
1. 0~i 回文 --> 0
2. 0~i 不回文 --> 0 < j < = i --> 若子串[ j, i ]回文 --> min(dp[ j - 1 ] + 1)
- 初始化：
dp表中所有元素初始化为Integer.MAX_VALUE
- 建表顺序：
从左往右
- 返回值：
dp[n-1]
4.2 算法代码
class Solution {
public int minCut(String ss) {
char[] s = ss.toCharArray();
int n = s.length;
boolean[][] isPal = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s[i] == s[j]) {
if (i == j)
isPal[i][j] = true;
else if (i + 1 == j)
isPal[i][j] = true;
else
isPal[i][j] = isPal[i + 1][j - 1];
}
}
}
int[] dp = new int[n];
// 初始化
Arrays.fill(dp, Integer.MAX_VALUE);
for (int i = 0; i < n; i++) {
if (isPal[0][i])
dp[i] = 0;
else {
// j --> (0, i]
for (int j = 1; j <= i; j++) {
if (isPal[j][i])
dp[i] = Math.min(dp[i], dp[j - 1] + 1);
}
}
}
return dp[n - 1];
}
}5、最长回文子序列
. - 力扣（LeetCode）
5.1 算法原理
- 状态表示：
dp[i][j]：s字符串[i , j]区间内的所有子序列中，最长回文子序列的长度
- 状态转移方程：
1. s[i] == s[j]：
i==j --> 1
i+1==j --> 2
dp[i+1][j-1]+2
2. s[i] != s[j]：
max(dp[i][j-1], dp[i+1][j])
- 初始化：
无需初始化
- 建表顺序：
从下往上填写每一行，每一行从左往右填写每一列
- 返回值：
dp[0][n-1]
5.2 算法代码
class Solution {
public int longestPalindromeSubseq(String ss) {
char[] s = ss.toCharArray();
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[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] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
}6、让字符串成为回文串的最少插入次数（hard）
. - 力扣（LeetCode）
6.1 算法原理
- 状态表示：
dp[i][j]：字符串[i, j]区间内的子串，使它成为回文串的最小插入次数
- 状态转移方程：
s[i] == s[j]：
1. i == j --> 0
2. i + 1 == j --> 0
3. dp[i + 1][j - 1]
s[i] != s[j]：
min(dp[i + 1][j], dp[i][j - 1]) + 1;
- 初始化：
无需初始化
- 建表顺序：
从上到下每一行
从左往右每一列
- 返回值：
dp[0][n-1]
6.2 算法代码
class Solution {
public int minInsertions(String ss) {
char[] s = ss.toCharArray();
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[i] == s[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];
}
}END