LeetCode 1312. 让字符串成为回文串的最少插入次数
目录
题目描述
题意分析
给一个只含小写字母的字符串
s，每次操作可以在任意位置（包括开头和结尾）插入任意一个字符，问最少插入多少次能让s变成回文串。先把题目要什么说清楚：只允许插入，不允许删除也不允许替换。这意味着原串的每一个字符都会原封不动地留在最终的回文串里，而且相对顺序不变。换句话说，答案里的原字符是最终回文串的一个子序列，我们只是往缝隙里塞新字符。
约束信号：
1 <= s.length <= 500。500 这个量级是典型的「二维状态表随便开」的信号，$O(n^2)$ 个状态、每个状态 $O(1)$ 转移完全跑得动，甚至 $O(n^3)$ 也勉强能过。反过来说，出题人并不指望你找到线性解法，而是希望你能把「插入」这件事翻译成一个可以递推的子结构。边界要想到几种：
s本身就是回文时答案为 0；长度为 1 时天然回文；字符两两互不相同时（比如abcde）必须补齐除中心外的每一个字符，答案是n - 1；s里有大量重复字符时答案会很小。还有一个容易读错的点：答案只要求次数，不要求你真的把那个回文串构造出来，所以不用记录插入的位置和内容。
解法：区间动态规划
核心思路
定义
dp[i][j]：把闭区间s[i..j]变成回文串的最少插入次数。只看两端即可决定如何缩小问题：
- 若
s[i] == s[j]，两端已经配对，dp[i][j] = dp[i + 1][j - 1]。- 若两端不同，至少要为其中一端插入一个镜像字符。保留左端后处理
s[i + 1..j]，或保留右端后处理s[i..j - 1]，所以dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1。长度为 0 或 1 的区间无需插入，初值为 0。按区间长度递增计算可保证依赖项已完成。两端不同时，上述两种插入覆盖了最优解的第一步；两端相同时，最优解没有理由额外拆散这对字符，因此转移完备且最优。
另一种等价视角是
答案 = n - 最长回文子序列长度，但直接区间 DP 更贴近题意。
解题步骤
- 创建
n × n的dp表，默认 0 正好覆盖空区间和单字符区间。- 从长度 2 开始枚举区间，再枚举左端点并算出右端点。
- 两端相同则继承内部区间；不同则在「为左端补镜像」和「为右端补镜像」对应的两个子问题中取较小值，再加 1。
- 返回
dp[0][n - 1]。例如
mbadm的两端m相同，答案继承中间bad；bad需要插入 2 次，因此最终答案是 2。长度为 2 且两端相等时会访问空区间位置，其默认值 0 正合语义。
代码实现
class Solution {
public int minInsertions(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int len = 2; len <= n; len++) {
for (int left = 0; left + len - 1 < n; left++) {
int right = left + len - 1;
if (s.charAt(left) == s.charAt(right)) {
dp[left][right] = dp[left + 1][right - 1];
} else {
// 两端不等时，只能补左端或补右端，选择代价更小的一侧。
dp[left][right] = Math.min(dp[left + 1][right], dp[left][right - 1]) + 1;
}
}
}
return dp[0][n - 1];
}
}
func minInsertions(s string) int {
n := len(s)
dp := make([][]int, n)
for idx := 0; idx < n; idx++ {
dp[idx] = make([]int, n)
}
for length := 2; length <= n; length++ {
for left := 0; left+length-1 < n; left++ {
right := left + length - 1
if s[left] == s[right] {
dp[left][right] = dp[left+1][right-1]
} else {
// 两端不等时，只能补左端或补右端，选择代价更小的一侧。
dp[left][right] = min(dp[left+1][right], dp[left][right-1]) + 1
}
}
}
return dp[0][n-1]
}
func min(first int, second int) int {
if first < second {
return first
}
return second
}
复杂度分析
- 时间复杂度：$O(n^2)$，共有平方级区间，每个状态 $O(1)$ 转移。
- 空间复杂度：$O(n^2)$，用于状态表；可进一步压缩到 $O(n)$。
关键点总结
- 状态必须表示闭区间的最少插入数，转移才具有清晰的子结构。
- 两端相同不加 1；两端不同只能补左或补右，取较小代价后加 1。
- 区间 DP 必须先算短区间，再算长区间。
- 等价公式是
n - LPS(s)，其中LPS为最长回文子序列，不是回文子串。
易错点总结
- 按左端点正序填表会在计算长区间时读到未完成状态；应按长度递增或左端点倒序。
- 两端相同时多加 1，会把
aa错算成 1。- 两端不同时转移到
dp[i + 1][j - 1]，等于假设一次插入能同时解决两端；abc会被错算为 1。- 不要把最长回文子序列误写成最长回文子串。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 5. 最长回文子串 | 中等 | 连续回文段的中心扩展 |
| 132. 分割回文串 II | 困难 | 回文分割的最少切割次数 |
| 516. 最长回文子序列 | 中等 | 本题的等价转化：n - L
|
| 647. 回文子串 | 中等 | 回文子串计数 |
| LCR 094. 分割回文串 II | 困难 | 分割回文串 II 的 LCR 版题号 |