让字符串成为回文串的最少插入次数 图解题解

这道题到底在问什么

输入

s = "zzazz"

输出

0(本身已是回文,一个都不用插)

输入

s = "mbadm"

输出

2(可插 2 个字符补成回文)

输入

s = "leetcode"

输出

5(最长回文子序列长度只有 3)

最优解：一步一步想明白

1. 3一句话套路:答案 = 长度减最长回文子序列;两端相同就内区间加 2,不同就丢一端取较大。下面逐格填表套这条规则。
2. 4先看骨架:行表示起点 i、列表示终点 j,格子 dp[i][j] 是子串 s[i..j] 的最长回文子序列长度。i > j 没意义(空区间),所以只填右上三角,现在全是「·」表示还没算。
3. 5为什么要按这个顺序?因为 dp[i][j] 用到的是更内层、更短的区间 dp[i+1][j-1] / dp[i+1][j] / dp[i][j-1]。只要让 i 从大到小、j 从小到大推,每次要用的内区间都已经算好了。先从对角线(单个字符)起步。
4. 6对角线 dp[4][4]:子串就是单个字符 "m",一个字符本身就是长度 1 的回文,所以 LPS = 1(紫格)。
5. 7对角线 dp[3][3]:子串就是单个字符 "d",一个字符本身就是长度 1 的回文,所以 LPS = 1(紫格)。
6. 8对角线 dp[2][2]:子串就是单个字符 "a",一个字符本身就是长度 1 的回文,所以 LPS = 1(紫格)。
7. 9对角线 dp[1][1]:子串就是单个字符 "b",一个字符本身就是长度 1 的回文,所以 LPS = 1(紫格)。
8. 10对角线 dp[0][0]:子串就是单个字符 "m",一个字符本身就是长度 1 的回文,所以 LPS = 1(紫格)。
9. 11区间 s[3..4] = "dm":两端 "d" 与 "m" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[4][4]=1;方案二丢右端,看 dp[3][3]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
10. 12区间 s[2..3] = "ad":两端 "a" 与 "d" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[3][3]=1;方案二丢右端,看 dp[2][2]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
11. 13区间 s[1..2] = "ba":两端 "b" 与 "a" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[2][2]=1;方案二丢右端,看 dp[1][1]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
12. 14区间 s[0..1] = "mb":两端 "m" 与 "b" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[1][1]=1;方案二丢右端,看 dp[0][0]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
13. 15区间 s[2..4] = "adm":两端 "a" 与 "m" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[3][4]=1;方案二丢右端,看 dp[2][3]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
14. 16区间 s[1..3] = "bad":两端 "b" 与 "d" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[2][3]=1;方案二丢右端,看 dp[1][2]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
15. 17区间 s[0..2] = "mba":两端 "m" 与 "a" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[1][2]=1;方案二丢右端,看 dp[0][1]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
16. 18区间 s[1..4] = "badm":两端 "b" 与 "m" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[2][4]=1;方案二丢右端,看 dp[1][3]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
17. 19区间 s[0..3] = "mbad":两端 "m" 与 "d" 不同,至少有一端进不了这段回文。方案一丢左端,看 dp[1][3]=1;方案二丢右端,看 dp[0][2]=1。取较大 = 1(两个候选一样,任选一边),填入紫格(蓝格是两个候选)。
18. 20区间 s[0..4] = "mbadm":两端都是 "m"!相同,这俩能当一层回文外壳。dp[0][4] = 内区间 dp[1][3]=1 + 2 = 3(紫格,蓝格是它依赖的内区间)。
19. 21上三角全部填好。右上角 dp[0][4] = 3 表示整个 "mbadm" 的最长回文子序列长度是 3(就是那段 "mam":m 配 m、中间留一个)。
20. 22回到原问题:总长 n = 5,能原地保留的回文骨架有 3 个字符,剩下 2 个落单字符各补一个镜像即可。最少插入次数 = 5 - 3 = 2。
21. 23复盘整条思路:先把「最少插入」转成「n 减最长回文子序列」;再用区间 DP,从短区间往长区间推,两端相同内区间加 2、不同取两侧最大;右上角即全串 LPS=3,答案 2。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        return n - dp[0][n - 1]

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; ++j) {
                dp[i][j] = s[i] == s[j] ? dp[i+1][j-1] + 2 : max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return n - dp[0][n-1];
    }
};

import java.util.*;
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--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) ? dp[i + 1][j - 1] + 2 : Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return n - dp[0][n - 1];
    }
}

复杂度

面试官可能追问