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

本文最后更新于：2022年9月22日 晚上

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

1
2
输入：s = "g"
输出：0

示例 5：

1
2
输入：s = "no"
输出：1

提示：

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

Solution

参考：《算法小抄》2.9

  • 状态转移方程
1
2
3
4
5
6
if (s[i]==s[j]){
    dp[i][j] = dp[i+1][j-1];
}
else{
    dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;
}

dp table

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# @lc code=start
class Solution:
    def minInsertions(self, s: str) -> int:
        n=len(s)
        dp=[[0 for _ in range(n)] for _ in range(n)]
        
        for i in range(n-2, -1, -1):
            for j in range(i+1, n):
                if s[i]==s[j]:
                    dp[i][j]=dp[i+1][j-1]
                else:
                    dp[i][j]=min(dp[i+1][j], dp[i][j-1])+1
        return dp[0][n-1]
# @lc code=end

状态压缩，一维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minInsertions(self, s: str) -> int:
        n=len(s)
        dp=[0]*n
        
        for i in range(n-2, -1, -1):
            pre=0
            for j in range(i+1, n):
                temp=dp[j]
                if s[i]==s[j]:
                    dp[j]=pre
                else:
                    dp[j]=min(dp[j], dp[j-1])+1
                pre=temp
        return dp[n-1]
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！