1312 Minimum Insertion Steps to Make a String Palindrome 让字符串成为回文串的最少插入次数

Description:

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

Example:

Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.

Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Constraints:

1 <= s.length <= 500
s consists of lowercase English letters.

题目描述：

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例：

示例 1：

输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。

示例 2：

输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

示例 3：

输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。

提示：

1 <= s.length <= 500
s 中所有字符都是小写字母。

思路：

1. 动态规划 - 最长子序列
   将字符串 s 反序得到 s'
   设 s 与 s‘ 的最长子序列为 m
   则 s 除了 m 以外的字符都需要添加到结果中
   比如 "leetcode" -> "edocteel", 两个字符串的最长子序列为 "ede"
   所以其他字符都需要添加到结果中变为 "leetcodocteel"
   设 dp[i][j] 表示 s[i:j] 与 s[i:j][::-1] 最长子序列的长度
   dp[i][i] = 1
   dp[i][j] = dp[i + 1][j - 1] + 2 if s[i] == s[j] else max(dp[i + 1][j], dp[i][j - 1])
   遍历需要从后往前遍历
   注意到 dp[i] 只和 dp[i + 1] 有关, 可以用滚动数组将空间复杂度压缩到O(n)
   时间复杂度为 O(n ^ 2), 空间复杂度为 O(n)
2. 动态规划
   设 dp[i][j] 表示使 s[i:j] 成为回文串需要的最少插入次数
   dp[i][j] = dp[i + 1][j - 1] if s[i] == s[j] else min(dp[i + 1][j], dp[i][j - 1]) + 1
   如果 s[i] != s[j], 则可以选择 s[i] 或者 s[j] 处插入字符
   注意到 dp[i] 只和 dp[i + 1] 有关, 可以用滚动数组将空间复杂度压缩到O(n)
   时间复杂度为 O(n ^ 2), 空间复杂度为 O(n)

代码:

C++:

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

Java:

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

Python:

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