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

Categories:

题目描述
思路分析
1. 解法一：区间动态规划（推荐）
相似题目

题目描述

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

思路分析

解法一：区间动态规划（推荐）

核心思路：

用 dp[i][j] 表示将子串 s[i..j] 变为回文串的最少插入次数。

若 s[i] == s[j]，则 dp[i][j] = dp[i+1][j-1]。

否则只能在两端插入，取 min(dp[i+1][j], dp[i][j-1]) + 1。

按区间长度从小到大递推，保证子问题先计算。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示字符串长度。

空间复杂度：O(n^2)，其中 n 表示字符串长度。

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 i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                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];
    }
}

func minInsertions(s string) int {
	n := len(s)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	for length := 2; length <= n; length++ {
		for i := 0; i+length-1 < n; i++ {
			j := i + length - 1
			if s[i] == s[j] {
				dp[i][j] = dp[i+1][j-1]
			} else {
				a := dp[i+1][j]
				b := dp[i][j-1]
				if a < b {
					dp[i][j] = a + 1
				} else {
					dp[i][j] = b + 1
				}
			}
		}
	}

	return dp[0][n-1]
}

相似题目

题目	难度	考察点
516. 最长回文子序列	中等	动态规划
131. 分割回文串	中等	回溯、动态规划
132. 分割回文串 II	困难	动态规划
647. 回文子串	中等	动态规划、中心扩展
5. 最长回文子串	中等	中心扩展、动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/82522983