难度: Hard
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例 1：
输入：s = "zzazz" 输出：0 解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
示例 2：
输入：s = "mbadm" 输出：2 解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
示例 3：
输入：s = "leetcode" 输出：5 解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
提示：
1 <= s.length <= 500s 中所有字符都是小写字母。运行时间: 138 ms
内存: 16.0 MB
class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
if n <= 1 or s[::-1] == s:
return 0
dp = [0]*n #这里表示从0到i的最长回文子序列长度
for i in range(n-1, -1, -1):
temp = 0 # dp[i] must be 0, so I use 0 instead of dp[i]
dp[i] = 1
for j in range(i+1, n):
if s[i] == s[j]:
temp, dp[j] = dp[j], temp + 2
else:
temp = dp[j]
if dp[j-1] > dp[j]:
dp[j] = dp[j-1]
return n - dp[-1]
本题解通过动态规划方法求解字符串成为回文串的最少插入次数。思路是先求出给定字符串的最长回文子序列的长度（使用动态规划表dp），然后用字符串的总长度减去这个最长回文子序列的长度，得到的结果即为最少的插入次数。动态规划表dp[i]表示从索引i到字符串末尾的子字符串中的最长回文子序列的长度。通过逐个比较字符，如果字符相同，则更新dp表；如果不同，则将dp[j]更新为dp[j]和dp[j-1]中的较大值。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
if n <= 1 or s[::-1] == s:
return 0
dp = [0]*n # dp数组，存储从i到n-1的最长回文子序列长度
for i in range(n-1, -1, -1):
temp = 0 # 临时变量，用于优化dp的更新过程
dp[i] = 1
for j in range(i+1, n):
if s[i] == s[j]:
temp, dp[j] = dp[j], temp + 2 # 如果s[i] == s[j], 更新dp[j]为temp + 2
else:
temp = dp[j]
if dp[j-1] > dp[j]:
dp[j] = dp[j-1] # 选择dp[j]和dp[j-1]中较大的值作为新的dp[j]
return n - dp[-1] # 返回需要插入的字符数量
在将一个字符串转换成回文串时，我们需要插入最少的字符数。一个有效的方法是找到字符串中已经存在的最长回文子序列，因为这部分字符不需要任何插入就已经满足回文的条件。剩余的字符需要通过插入操作来配对，确保整个字符串成为回文。因此，需要插入的字符数等于总字符数减去最长回文子序列的长度，这样就补全了不在回文子序列中的字符，并使整个字符串成为回文。
在动态规划的过程中，temp变量被用来暂存旧的dp[j]值，在计算新的dp[j]时使用。当s[i]等于s[j]时，我们需要用到i到j-1子字符串的dp值来更新dp[j]。在更新dp[j]之前，temp保存了原始的dp[j]，以便在后续循环中使用旧值进行比较和计算。这样做是为了避免在同一轮循环中使用已经更新过的dp值，保证计算的正确性。
在这个问题的动态规划解法中，dp数组的每个元素代表对应索引开始到字符串末尾的最长回文子序列的长度。由于字符串中的任何单个字符都是一个长度为1的回文子序列，因此初始化dp数组的每个元素为1是合理的。这表示即使在最不利的情况下，即从任何索引开始的子字符串至少包含一个字符，即它自身，也是一个有效的回文子序列。
代码中的外层循环从字符串的末尾向前遍历，保证在更新dp[j]时，所有需要参考的dp值(dp[j+1]等)已经计算并存储好了。内层循环则从i开始向字符串末尾遍历，每次比较s[i]和s[j]。如果字符相同，则利用已知的dp值更新当前dp[j]，反映从i到j的最长回文子序列长度。如果字符不同，则dp[j]被更新为其自身或其左侧元素dp[j-1]的较大值，确保dp[j]始终保持当前最长的回文子序列长度。这种从后向前的更新保证了在计算每个dp[j]时，所需的所有相关dp值都是最新的，并准确反映了各个子字符串的情况。