LeetCode 1312. 让字符串成为回文串的最少插入次数

约 4 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 10-20 腾讯 字节 微软 快手 图森
标签
字符串 动态规划

题目描述

✅ 1312. 让字符串成为回文串的最少插入次数

image-20260928215048073

image-20260928215048074

题意分析

只能插入字符，不能删除、替换或调整原字符的顺序，求把整个字符串补成回文所需的最少次数。题目保证字符串非空，单个字符已经是回文，不需要插入。

解法：区间动态规划

核心思路

[!blue]

回文要求两端字符相同。先决定当前区间的两端如何配对，剩下的仍然是一个连续区间，因此可以用区间动态规划。

定义 dp[left][right] 为把闭区间 s[left..right] 补成回文的最少插入次数。空区间和单字符本来就是回文，代价为 0。

如果 s[left] == s[right]，两个已有字符可以直接配成最外层，只需把中间补成回文，得到 dp[left][right] = dp[left + 1][right - 1]。为这两个相同端点另补字符不会更省，因此不必枚举这种选择。

如果两端不同，它们无法互相配对。原字符的相对顺序不能变，所以至少有一个端点必须与新插入的字符配对：在右侧补一个 s[left]，剩余问题是 s[left + 1..right]；或者在左侧补一个 s[right]，剩余问题是 s[left..right - 1]。两种选择各花一次插入，因此取 min(dp[left + 1][right], dp[left][right - 1]) + 1。

每次配对都留下更短的区间。短区间的最优答案确定后，枚举这两种必要选择就能得到长区间的最优答案；按长度递增计算即可。

解题步骤

  1. 创建 n × n 的 dp 表，单字符区间 dp[i][i] 保持为 0。
  2. 从长度 2 开始枚举区间，再枚举左端点并算出右端点。
  3. 两端相同，继承内部区间的代价；两端不同，比较补左端的镜像与补右端的镜像，选择代价较小的一种。
  4. 返回整个字符串对应的 dp[0][n - 1]。

长度为 2 且两端相等时，内部为空，会读取 dp[left + 1][left]。这个位置仍在数组范围内，保留的默认值 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)$，用于状态表。

关键点总结

[!green]

  • 状态只记录尚未完成配对的区间，已配好的端点不再参与子问题。
  • 两端相同可直接配对；两端不同至少要补一个字符，分别尝试为左端或右端配对。
  • 转移依赖更短区间，所以从长度 2 开始向外扩展。

易错点总结

[!yellow]

  • 子问题去掉一个端点不表示删除原字符，而是它已经与插入的镜像字符配好。
  • 两端不同时不能直接转移到 dp[left + 1][right - 1] + 1：一个新字符无法同时与两个不同的端点配对。
  • 两端相同不增加插入次数；单字符和空区间的代价也都是 0。
  • 若改成左端点正序作为最外层，可能读到尚未计算的 dp[left + 1][right]；当前按长度递增没有这个问题。

相似题目

题目 难度 关联与区别
516. 最长回文子序列 中等 保留最长回文子序列，其他位置补入对应字符，最少插入次数为串长减LPS长度。
72. 编辑距离 中等 原题允许多种编辑，本题只能插入，不能把普通编辑距离直接当答案。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/82522983
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！