题目描述
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
“回文串”是正读和反读都相同的字符串。
样例
-
示例 1：
输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。 -
示例 2：
输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。 -
示例 3：
输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。 -
示例 4：
输入：s = "g"
输出：0 -
示例 5：
输入：s = "no"
输出：1
- 提示：
1 <= s.length <= 500
s 中所有字符都是小写字母。
题目评估
知识点：动态规划
难度：困难（虽然本题和昨天的题代码几乎一样，但是思考过程比较困难）
分析
现在我们有一个现成的字符串s，我们要通过插入一些字符让它变成回文，如何使插入的字符最少呢？要想插入的少，就要忽略已经是回文的子序列，OK！那么我们只要找到最长的回文子序列，再用字符串s的长度减去最长回文子序列的长度就是我们要插入的字符数量，因为我们只有再插入这么多字符，才能让整个字符串s变成回文！是不是和昨天的题有点类似？昨天的题就是找到一个字符串的最长回文子序列的长度。我们把昨天的方法拿过来用一下，答案就信手拈来了。
Java代码题解
class Solution {
public int minInsertions(String s) {
// 如果长度为0或1直接返回0，因为不需要任何操作它本身就是回文
if (s == null || s.length() == 0 || s.length() == 1) {
return 0;
}
// 用该字符串本身的长度减去最长回文子序列就是本题的答案
int res = s.length() - longestPalindromeSubseq(s);
return res;
}
public int longestPalindromeSubseq(String s) { // 这是力扣第516题的题解
// 定义一个字符串长度*字符串长度的二维数组，用来保存子串的最大回文子序列长度
int[][] dp = new int[s.length()][s.length()];
for (int i = dp.length - 1; i >= 0; i--) { // i从最后一个开始遍历
dp[i][i] = 1; // 初始化，每个字符都是长度为一的回文
for (int j = i + 1; j < dp[i].length; j++) { // j从第i+1个开始遍历
if (s.charAt(i) == s.charAt(j)) { // 如果子串的两头字符相等
// 该子串掐掉两头后的子串最大子回文序列长度+2就是该子串的最大回文子序列长度
dp[i][j] = dp[i + 1][j - 1] + 2;
} else { // 如果该子串两头字符不相等
// 该子串的两个掐掉一头的子串最大回文子序列长度，哪个最大，就取哪个赋给该子串最大回文子序列长度
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
}
}
}
// 最后返回整个字符串的最大回文子序列长度
return dp[0][dp[0].length - 1];
}
}
复杂度分析
和昨天的题一样：
设n表示字符串长度，双层遍历一个二维数组，时间复杂度为O(n^2)
开辟了一个n*n的二维数组，空间复杂度为O(n^2)