Leetcode 1312：让字符串成为回文串的最少插入次数（超详细的解法！！！）

给你一个字符串 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 中所有字符都是小写字母。

解题思路

这个问题其实不难，我们可以定义函数$f(l,r)$f(l,r)表示字符串s[l:r+1]变成回文串的最少插入次数。那么如果s[l]==s[r]，那么$f(l,r)=f(l+1,r-1)$f(l,r)=f(l+1,r−1)。否则此时两个字符不同，那么需要插入字符。这里有两种插入方式，一种是左边插入$f(l,r-1)$f(l,r−1)，另一种是右边插入$f(l+1,r)$f(l+1,r)，所以$f(l,r)=1+min(f(l+1,r),f(l,r-1))$f(l,r)=1+min(f(l+1,r),f(l,r−1))。

from functools import lru_cache
class Solution:
    def minInsertions(self, s: str) -> int:
        @lru_cache(None)
        def dfs(l, r):
            if l >= r:
                return 0
            
            if s[l] == s[r]:
                return dfs(l + 1, r - 1)
            return 1 + min(dfs(l + 1, r), dfs(l, r - 1))
            
        return dfs(0, len(s) - 1)

同样可以写出动态规划的形式：

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

这个问题和Leetcode 1216：验证回文字符串 III（超详细的解法！！！）是一样的，之前问题是最少删除，这个问题是最少添加（两者是对称的）。

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

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！