【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 中所有字符都是小写字母。

二、解题思路 & 代码

定义一个二维的 $d p$ 数组， $d p [i] [j]$ 的定义如下：对字符串 $s [i . . j]$ ，最少需要进行 $d p [i] [j]$ 次插入才能变成回文串。

我们想求整个 s 的最少插入次数，根据这个定义，也就是想求 $d p [0] [n - 1]$ 的大小（n为s的长度）。

同时，base case 也很容易想到，当 $i = = j$ 时 $d p [i] [j] = 0$ ，因为当 $i = = j$ 时 $s [i . . j]$ 就是一个字符，本身就是回文串，所以不需要进行任何插入操作。

1、如果s[i] == s[j]

如果s[i] == s[j]的话，我们不需要进行任何插入，只要知道如何把s[i+1…j-1]变成回文串即可：

if (s[i] == s[j])：
    dp[i][j] = dp[i + 1][j - 1]

2、如果s[i] != s[j]

最优的插入方案应该被拆解成如下流程：

步骤一，做选择，先将s[i…j-1]或者s[i+1…j]变成回文串。怎么做选择呢？谁变成回文串的插入次数少，就选谁呗。

比如图二的情况，将s[i+1…j]变成回文串的代价小，因为它本身就是回文串，根本不需要插入；同理，对于图三，将s[i…j-1]变成回文串的代价更小。

然而，如果 s[i+1…j] 和 s[i…j-1] 都不是回文串，都至少需要插入一个字符才能变成回文，所以选择哪一个都一样：

那我怎么知道s[i+1…j]和s[i…j-1]谁变成回文串的代价更小呢？

回头看看dp数组的定义是什么，dp[i+1][j] 和 dp[i][j-1] 不就是它们变成回文串的代价么？

步骤二，根据步骤一的选择，将 s[i…j] 变成回文。

如果你在步骤一中选择把 s[i+1…j] 变成回文串，那么在 s[i+1…j] 右边插入一个字符 s[i] 一定可以将 s[i…j] 变成回文；同理，如果在步骤一中选择把 s[i…j-1] 变成回文串，在 s[i…j-1] 左边插入一个字符 s[j] 一定可以将 s[i…j] 变成回文。

那么根据刚才对dp数组的定义以及以上的分析，s[i] != s[j]时的代码逻辑如下：

if (s[i] != s[j])：
    #步骤一选择代价较小的
    # 步骤二必然要进行一次插入
    dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1

代码实现

因为状态转移方程中 $d p [i] [j]$ 和 $d p [i + 1] [j]$ ， $d p [i] - 1]$ ， $d p [i + 1] [j - 1]$ 三个状态有关，为了保证每次计算 $d p [i] [j]$ 时，这三个状态都已经被计算，我们一般选择从下向上，从左到右遍历 dp数组：

二维 dp

class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        # 定义：对 s[i..j]，最少需要插入 dp[i][j] 次才能变成回文
        dp = [[0] * n for i in range(n)]
        # base case：i == j 时 dp[i][j] = 0，单个字符本身就是回文
        # dp 数组已经全部初始化为 0，base case 已初始化

        # 从下向上遍历
        for i in range(n-2, -1, -1):
            # 从左向右遍历
            for j in range(i+1, n):
                # 根据 s[i] 和 s[j] 进行状态转移
                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 数组的定义，题目要求的答案
        return dp[0][n - 1]

复杂度分析：

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

一维 dp

class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        dp = [0] * n
        temp = 0
        for i in range(n-2, -1, -1):
            # 记录 dp[i+1][j-1]
            pre = 0
            for j in range(i+1, n):
                temp = dp[j]
                if (s[i] == s[j]):
                    # dp[i][j] = dp[i+1][j-1]
                    dp[j] = pre
                else:
                    # dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
                    dp[j] = min(dp[j], dp[j - 1]) + 1

                pre = temp

        return dp[n - 1]

复杂度分析：

时间复杂度： $O(n^2)$
空间复杂度： $O (n)$

参考：

(公众号文章)回文问题终极篇：最小代价构造回文串