使字符串成为回文串的最少插入次数

问题描述

给定一个字符串 s，你可以在任意位置插入任意字符。请计算最少需要插入多少个字符，才能使 s 变成一个回文串。

示例：

• 输入：s = "zzazz"
  输出：0
  解释：字符串本身就是回文串，无需插入。
• 输入：s = "mbadm"
  输出：2
  解释：字符串可以变成 "mbdadbm" 或 "mdbabdm"，最少插入 2 个字符。
• 输入：s = "leetcode"
  输出：5
  解释：插入 5 个字符后可以变成 "leetcodocteel" 等回文串。

解题思路

这是一个经典的线性动态规划问题，核心是寻找字符串的最长回文子序列。因为要使插入的字符最少，我们应该尽量保留原字符串中的字符，通过插入来补全那些无法配对成回文的字符。
关键发现：一个字符串变成回文串所需的最少插入次数，等于该字符串长度减去其最长回文子序列（LPS）的长度。
为什么呢？

• 最长回文子序列已经是原字符串中能构成回文的最长子序列。
• 对于不在这个子序列中的字符，我们需要插入一个对称的字符来与之匹配。
• 因此，总插入次数 = 字符串长度 - LPS长度。

接下来，问题转化为求字符串 s 的最长回文子序列的长度。我们可以使用动态规划来解决。

动态规划解法步骤

定义 dp[i][j] 为字符串 s 在区间 [i, j]（闭区间）的最长回文子序列的长度。
最终答案是 len(s) - dp[0][n-1]，其中 n 是字符串长度。

状态转移方程

1. 基础情况：当区间长度为 1（即 i == j）时，单个字符本身就是回文，所以 dp[i][j] = 1。
2. 状态转移：
   • 如果 s[i] == s[j]，那么这两个字符可以同时作为回文子序列的两端，因此 dp[i][j] = dp[i+1][j-1] + 2。
   • 如果 s[i] != s[j]，那么这两个字符不能同时作为两端，我们只能选择其中一个或不选，因此 dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

填表顺序

由于 dp[i][j] 依赖于 dp[i+1][j-1]、dp[i+1][j] 和 dp[i][j-1]，即左下方、正下方和左方的值，因此我们需要从下往上、从左往右填表，或者按照区间长度从小到大的顺序。

详细计算过程

以 s = "mbadm" 为例，n = 5。

1. 初始化：所有单个字符的区间 dp[i][i] = 1。
   表初始状态（dp[i][j] 表示从 i 到 j 的最长回文子序列长度）：

   i\j 0 1 2 3 4
    0  1 0 0 0 0
    1    1 0 0 0
    2      1 0 0
    3        1 0
    4          1
   

2. 计算长度 = 2 的区间：

   • [0,1]：s[0]='m', s[1]='b'，不相等，dp[0][1] = max(dp[1][1], dp[0][0]) = max(1,1) = 1。
   • [1,2]：s[1]='b', s[2]='a'，不相等，dp[1][2] = max(dp[2][2], dp[1][1]) = max(1,1) = 1。
   • [2,3]：s[2]='a', s[3]='d'，不相等，dp[2][3] = max(dp[3][3], dp[2][2]) = max(1,1) = 1。
   • [3,4]：s[3]='d', s[4]='m'，不相等，dp[3][4] = max(dp[4][4], dp[3][3]) = max(1,1) = 1。
     更新表：

   i\j 0 1 2 3 4
    0  1 1 0 0 0
    1    1 1 0 0
    2      1 1 0
    3        1 1
    4          1
   

3. 计算长度 = 3 的区间：

   • [0,2]：s[0]='m', s[2]='a'，不相等，dp[0][2] = max(dp[1][2], dp[0][1]) = max(1,1) = 1。
   • [1,3]：s[1]='b', s[3]='d'，不相等，dp[1][3] = max(dp[2][3], dp[1][2]) = max(1,1) = 1。
   • [2,4]：s[2]='a', s[4]='m'，不相等，dp[2][4] = max(dp[3][4], dp[2][3]) = max(1,1) = 1。
     更新表：

   i\j 0 1 2 3 4
    0  1 1 1 0 0
    1    1 1 1 0
    2      1 1 1
    3        1 1
    4          1
   

4. 计算长度 = 4 的区间：

   • [0,3]：s[0]='m', s[3]='d'，不相等，dp[0][3] = max(dp[1][3], dp[0][2]) = max(1,1) = 1。
   • [1,4]：s[1]='b', s[4]='m'，不相等，dp[1][4] = max(dp[2][4], dp[1][3]) = max(1,1) = 1。
     更新表：

   i\j 0 1 2 3 4
    0  1 1 1 1 0
    1    1 1 1 1
    2      1 1 1
    3        1 1
    4          1
   

5. 计算长度 = 5 的区间（整个字符串）：

   • [0,4]：s[0]='m', s[4]='m'，相等，所以 dp[0][4] = dp[1][3] + 2。
     先看 dp[1][3]，我们在第三步已经算出为 1。
     因此 dp[0][4] = 1 + 2 = 3。
     最终表：

   i\j 0 1 2 3 4
    0  1 1 1 1 3
    1    1 1 1 1
    2      1 1 1
    3        1 1
    4          1
   

6. 最少插入次数：
   最长回文子序列长度 = dp[0][4] = 3。
   字符串长度 = 5。
   最少插入次数 = 5 - 3 = 2。

算法实现要点

• 时间复杂度：O(n²)，因为需要填充一个 n x n 的二维 DP 表。
• 空间复杂度：可以优化到 O(n) 使用一维数组，因为填表时只依赖于上一行和当前行的左边值，但保留二维思路更清晰。
• 边界情况：空字符串或单字符字符串时，插入次数为 0。

总结

本问题通过转化为求最长回文子序列，巧妙地利用了动态规划。核心是理解“最少插入次数”与“最长回文子序列长度”的互补关系，然后通过区间 DP 计算出 LPS 长度，从而得到答案。这种方法避免了直接思考插入位置的复杂性，体现了动态规划将复杂问题分解为子问题的强大能力。