Leetcode 1312:让字符串成为回文串的最少插入次数(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1312:让字符串成为回文串的最少插入次数(超详细的解法!!!)

in leetcode with 0 comment

给你一个字符串 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

提示:

解题思路

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

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses