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

题目

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。

示例：

  1. 输入：s = "zzazz"
  2. 输出：0
  3. 解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

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

解答 & 代码

解法一：len - 最长回文子序列长度

  1. 让字符串 s 成为回文串的最少插入次数 = 字符串 s 长度 - s 的最长回文子序列长度
  2. 求最长回文子序列长度：等价于求 s 及其反转字符串 reverseS 的最长公共子序列长度
  3. 求两个字符串的最长公共子序列长度：二维 dp

[中等] 1143. 最长公共子序列

class Solution {
public:
    int minInsertions(string s) {
        int len = s.size();
        string reverseS = s;
        reverse(reverseS.begin(), reverseS.end());
        vector<vector<int>> dp(len + 1, vector<int>(len + 1, 0));
        for(int i = 1; i <= len; ++i)
        {
            for(int j = 1; j <= len; ++j)
            {
                if(s[i - 1] == reverseS[j - 1])
                    dp[i][j] = max(dp[i - 1][j - 1] + 1, max(dp[i - 1][j], dp[i][j - 1]));
                else
                    dp[i][j] = max(dp[i - 1][j - 1], max(dp[i - 1][j], dp[i][j - 1]));
            }
        }
        return len - dp[len][len];
    }
};

复杂度分析：设字符串 s 长为 N

  • 时间复杂度[困难] 1312. 让字符串成为回文串的最少插入次数 - 图1：
  • 空间复杂度[困难] 1312. 让字符串成为回文串的最少插入次数 - 图2：

执行结果：

执行结果：通过

执行用时：104 ms, 在所有 C++ 提交中击败了 7.51% 的用户
内存消耗：26.5 MB, 在所有 C++ 提交中击败了 11.02% 的用户

解法二：区间动态规划