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

题目描述

输入字符串 s。每次操作可以在任意位置插入一个任意字符。

回文串是正着读和倒着读都一样的字符串。返回把 s 变成回文串所需的最少操作次数。

示例 1

输入：s = "zzazz"
输出：0

解释：zzazz 本身就是回文串。

示例 2

输入：s = "mbadm"
输出：2

解释：插入两个字符可以得到 mbdadbm 或 mdbabdm。

示例 3

输入：s = "leetcode"
输出：5

解释：插入 5 个字符可以得到 leetcodocteel。

数据范围

1 <= s.length <= 500
s 只含小写字母。

解题思路：区间动态规划

设 dp[i][j] 为把子串 s[i..j] 变成回文的最少插入次数。两端字符相同，它们可以直接配对，答案等于内部 dp[i+1][j-1]；两端不同，必须为其中一端补一个对称字符：补 s[i] 后剩下 s[i+1..j]，补 s[j] 后剩下 s[i..j-1]，取较小者再加 1。按区间从短到长（i 从大到小、j 从小到大）填表。

为什么正确

计算 dp[i][j] 时，它依赖的三个更短区间 dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1] 都已经算好；单个字符和空区间的值为 0。

复杂度分析

时间 O(n^2)，空间 O(n^2)。

易错点

填表顺序容易写错：i 必须从大到小，否则 dp[i+1][...] 还没算出来。另外两端相同时直接继承内部结果，不需要再和其他两项比较取最小。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

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

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[0][n - 1];
    }
}

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[0][n - 1];
    }
};

func minInsertions(s string) int {
	n := len(s)
	dp := make([][]int, n)
	for k := range dp {
		dp[k] = make([]int, n)
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if s[i] == s[j] {
				dp[i][j] = dp[i+1][j-1]
			} else {
				dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
			}
		}
	}
	return dp[0][n-1]
}

var minInsertions = function(s) {
    const n = s.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let i = n - 2; i >= 0; i--) {
        for (let j = i + 1; j < n; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
            }
        }
    }
    return dp[0][n - 1];
};

function minInsertions(s: string): number {
    const n = s.length;
    const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let i = n - 2; i >= 0; i--) {
        for (let j = i + 1; j < n; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
            }
        }
    }
    return dp[0][n - 1];
}

载入编辑器，自己跑一遍 →

其他解法

区间 DP 直接定义“把 s[i..j] 变成回文的最少插入次数”，按区间长度递推；LCS 方法先把问题转化为最长回文子序列，再转化为与反转串的公共子序列，体现了问题归约的思路。两者时间复杂度相同。

解法 2：转化为与反转串的最长公共子序列时间 O(n²)，空间 O(n)

插入字符后保留下来的原字符一定构成一个回文子序列，而且最长的回文子序列需要的插入最少，所以答案是 n 减去最长回文子序列的长度。字符串 s 的最长回文子序列恰好等于 s 和它的反转串的最长公共子序列，于是直接套用 LCS 的动态规划，并用一维数组滚动保存。

把新问题归约到熟悉的 LCS 模板，只要证明“最少插入 = n − 最长回文子序列”即可，代码可以完全复用，空间也能压到一维。需要额外理解这两步转化，不如区间 DP 直接。

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

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        String t = new StringBuilder(s).reverse().toString();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int prev = 0;
            for (int j = 1; j <= n; j++) {
                int tmp = dp[j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) dp[j] = prev + 1;
                else dp[j] = Math.max(dp[j], dp[j - 1]);
                prev = tmp;
            }
        }
        return n - dp[n];
    }
}

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        string t(s.rbegin(), s.rend());
        vector<int> dp(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            int prev = 0;
            for (int j = 1; j <= n; j++) {
                int tmp = dp[j];
                if (s[i - 1] == t[j - 1]) dp[j] = prev + 1;
                else dp[j] = max(dp[j], dp[j - 1]);
                prev = tmp;
            }
        }
        return n - dp[n];
    }
};

func minInsertions(s string) int {
	n := len(s)
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		prev := 0
		for j := 1; j <= n; j++ {
			tmp := dp[j]
			if s[i-1] == s[n-j] {
				dp[j] = prev + 1
			} else {
				dp[j] = max(dp[j], dp[j-1])
			}
			prev = tmp
		}
	}
	return n - dp[n]
}

var minInsertions = function(s) {
    const n = s.length;
    const t = s.split('').reverse().join('');
    const dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        let prev = 0;
        for (let j = 1; j <= n; j++) {
            const tmp = dp[j];
            if (s[i - 1] === t[j - 1]) dp[j] = prev + 1;
            else dp[j] = Math.max(dp[j], dp[j - 1]);
            prev = tmp;
        }
    }
    return n - dp[n];
};

function minInsertions(s: string): number {
    const n = s.length;
    const t = s.split('').reverse().join('');
    const dp: number[] = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        let prev = 0;
        for (let j = 1; j <= n; j++) {
            const tmp = dp[j];
            if (s[i - 1] === t[j - 1]) dp[j] = prev + 1;
            else dp[j] = Math.max(dp[j], dp[j - 1]);
            prev = tmp;
        }
    }
    return n - dp[n];
}

动态规划专题的其他题目

查看动态规划全部题目 →