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

Difficulty
Hard
Tags
动态规划
URL
https://leetcode-cn.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
Star
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例 1：
输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
示例 2：
输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
示例 3：
输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
示例 4：
输入：s = "g"
输出：0
示例 5：
输入：s = "no"
输出：1
提示：
  • 1 <= s.length <= 500
  • s 中所有字符都是小写字母。

法1 动态规划双序列型

思路
题目要求将序列s变为回文串需要最少插入字符的个数。那么我再构造一个字符串t,令t为s的逆序。这样问题就变成了使t和s相同需要插入的字符个数。那么就等同于求这两个字符串的shortest common supersequence (SCS)，然后减掉本身的序列长度即可。
这个转换其实并不容易理解。我们只能大概地有一种直观的感受：因为s和t是逆序关系，s最后一个字符等于t的第一个字符，应该让s放置于t的前面，尽可能地重合s的尾部和t的头部来提高字符重用的利用效率。所以最终s和t的SCS应该是个回文串。既然SCS的第一个S是shortest的意思，那么这个SCS就是通过s可以得到的最短的回文串。
题解
class Solution:
    def minInsertions(self, s: str) -> int:
        t = s[::-1]

        dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
        
        for i in range(len(dp)):
            dp[i][0] = i
        for j in range(len(dp[0])):
            dp[0][j] = j        

        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1])+1
       
        return dp[-1][-1] - len(s)

法2 动态规划

思路
题目要求将序列s变为回文串需要最少插入字符的个数。那么我再构造一个字符串t,令t为s的逆序。
这样就变成 是的s 和 t 两个字符串相同的最少插入次数了。
本体区别于编辑距离，本题只允许插入，而不能删除或替换。
此外，最后计算出来的是，两个字符串一共需要插入的次数，所以需要除2
题解
class Solution:
    def minInsertions(self, s: str) -> int:
        if len(s) <= 1:
            return 0

        t = s[::-1]

        s = "#" + s
        t = "#" + t

        dp = [[0]* len(t) for _ in range(len(s))]

        for i in range(1, len(s)):
            dp[i][0] = i
        for j in range(1, len(t)):
            dp[0][j] = j

        for i in range(1, len(s)):
            for j in range(1, len(s)):
                if s[i] == t[j]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1

        # 因为算的是 s 和 t 两个字符串一共需要插入的次数，所以这里 // 2
        return dp[-1][-1] // 2