加载中...
1312-让字符串成为回文串的最少插入次数(Minimum Insertion Steps to Make a String Palindrome)
发表于:2021-12-03 | 分类: 困难
字数统计: 3k | 阅读时长: 12分钟 | 阅读量:

原文链接: https://leetcode-cn.com/problems/minimum-insertion-steps-to-make-a-string-palindrome

英文原文

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

Palindrome String is one that reads the same backward as well as forward.

 

Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.

Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Example 4:

Input: s = "g"
Output: 0

Example 5:

Input: s = "no"
Output: 1

 

Constraints:

  • 1 <= s.length <= 500
  • All characters of s are lower case English letters.

中文题目

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

通过代码

高赞题解

方法一:动态规划

设我们通过最少的操作次数将字符串 s 变成了回文串 s',根据 s' 长度的奇偶性,会有如下的两种情况:

  • s' 的长度为奇数,那么它的回文中心为单个字符 c。例如当 s' = "adgda" 时,它的回文中心为单个字符 "g"。我们可以断定,回文中心 c 一定是原字符串 s 中的字符,否则如果 c 是通过操作添加的字符,那么我们可以舍弃这一步操作,此时 s' 成为长度为偶数的字符串,并且它仍是回文串(在例子中,即 "adgda" -> "adda")。

  • s' 的长度为偶数,那么它的回文中心为两个字符 cc,例如当 s' = "adggda" 时,它的回文中心为两个字符 "gg"。我们同样可以断定,回文中心 cc 一定是原字符串中的两个字符,否则如果 cc 中有至少一个是通过操作添加的字符,那么我们可以舍弃这些操作,此时 s' 成为长度为偶数(舍弃一次操作)或奇数(舍弃两次操作)的字符串,并且它仍是回文串(在例子中,即 "adggda" -> "adgda""adggda" -> "adda")。

    • 根据此断定,我们还可以得到一条推论,即回文中心 cc 一定是原字符串中的两个连续的字符。这是因为我们的操作只能添加字符而不能删除字符,因此在回文中心 cc 是原字符串中的两个字符的情况下,它们一定也是连续的。

这样以来,我们可以首先枚举回文中心(单个字符或两个字符),再对回文中心左侧的字符串 p 和右侧的字符串 q 进行相应的操作。具体地,我们希望通过最少的操作次数(添加最少的字符),使得 inv(p)q 变成相同的字符串,其中 inv(p) 表示将字符串 p 翻转之后得到的字符串,例如当 p = "abcd" 时,inv(p) = "dcba"

那么如何解决这个子问题呢?我们首先用 inv(p) 代替 p,这样我们的子问题变成:添加最少的字符,使得 pq 变成相同的字符串。此时答案就变得十分明朗了,我们只需要得到 pq 的最长公共子序列,设其长度为 l,那么最少添加 |p| + |q| - l * 2 个字符,就可以将 pq 变成相同的字符串。例如:

p = "abcde"q = "adefg" 时,他们的最长公共子序列为 "ade",长度为 3。此时我们可以将 pq 和它们的最长公共子序列写成如下的形式:

p = a b c d e
q = a     d e f g
    a     d e

可以看出,以最长公共子序列为基础,我们只需要在 "a""d" 之间添加字符 "bc",在 "d" 之后添加字符 "fg",得到的字符串 "abcdefg" 就是 pq 变成的相同字符串,即我们在 pq 中分别添加 2 个字符,就可以得到该字符串。另一方面,|p| + |q| - l = 5 + 5 - 3 * 2 = 4,即我们一共需要添加 4 个字符,这两个值相等。

枚举回文中心的时间复杂度为 $O(N)$,而计算两个字符串的最长公共子序列的时间复杂度为 $O(N^2)$,那么整个算法的时间复杂度为 $O(N^3)$,无法在规定的时间内通过本题。我们必须要对算法进行一些优化。

仔细回想一下算法的过程,我们依次进行了如下的两个步骤:

  • 枚举回文中心,并得到回文中心左右两侧的字符串 pq

  • 计算 inv(p)q 的最长公共子序列。

我们能否把这两个步骤合并起来呢?这两个步骤到底得到了什么结果?

如果我们将 inv(p)q 的最长公共子序列设为 r,那么在这两个步骤之后,我们在 inv(p) 中得到了 inv(r)q 中得到了 r,并且得到了回文中心 ccc。我们将这三个部分拼在一起,实际上得到了一个回文串 inv(r) + c/cc + r,并且它是原字符串 s 的一个子序列!这个回文串越长,就意味着我们需要添加的字符越少。也就是说,我们需要在原字符串 s 中找到一个最长回文子序列,若其长度为 l,那么我们只需要添加 |s| - l 个字符,就可以将 s 变为回文串。

如何从直观上来理解它呢?当我们在原字符串 s 中找到最长回文子序列后,对于在 s 中但不在子序列中的那些字符,如果其在回文中心的左侧,我们就在右侧对应的位置添加一个相同的字符;如果其在回文中心的右侧,我们就在左侧对应的位置添加一个相同的字符。例如:

s = "dabca" 时,它的最长回文子序列为 "aba",我们将 s 写成如下的形式:

      a   b   a       (回文中心为 b)
s = d a   b c a
s = d a   b c a d     (字符 d 在回文中心左侧,那么在右侧对应位置添加一个相同的字符)
s = d a c b c a d     (字符 c 在回文中心右侧,那么在左侧对应位置添加一个相同的字符)

我们添加了 2 个字符将 s 变为回文串。另一方面,|s| - l = 5 - 3 = 2,这两个值相等。

那么如何求出 s 的最长回文子序列 sPA 呢?实际上,sPA 就等同于 sinv(s) 的最长公共子序列,即 sPA 既是 s 的子序列,也是 inv(s) 的子序列(这样就保证了 sPA 是一个回文的子序列)。这样以来,我们只要在 $O(N^2)$ 的时间求出 sinv(s) 的最长公共子序列,根据它的长度 l,通过 |s| - l 就可以得到答案。

关于「最长公共子序列」或「最长回文子序列」的更多信息,可以参考力扣对应的两道题目:

[sol1-C++]
class Solution { public: int minInsertions(string s) { int n = s.size(); string t(s.rbegin(), s.rend()); vector<vector<int>> dp(n + 1, vector<int>(n + 1)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); if (s[i - 1] == t[j - 1]) { dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1); } } } return n - dp[n][n]; } };
[sol1-Python3]
class Solution: def minInsertions(self, s: str) -> int: n = len(s) t = s[::-1] dp = [[0] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, n + 1): dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) if s[i - 1] == t[j - 1]: dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1) return n - dp[n][n]

复杂度分析

  • 时间复杂度:$O(N^2)$,其中 $N$ 是字符串 s 的长度。

  • 空间复杂度:$O(N^2)$。

方法二:区间动态规划

除了方法一之外,我们也可以使用经典的区间动态规划方法来解决本题,并且这种方法更加直观。

我们用 dp[i][j] 表示对于字符串 s 的子串 s[i:j](这里的下标从 0 开始,并且 s[i:j] 包含 s 中的第 i 和第 j 个字符),最少添加的字符数量,使得 s[i:j] 变为回文串。

我们从外向内考虑 s[i:j]

  • 如果 s[i] == s[j],那么最外层已经形成了回文,我们只需要继续考虑 s[i+1:j-1]

  • 如果 s[i] != s[j],那么我们要么在 s[i:j] 的末尾添加字符 s[i],要么在 s[i:j] 的开头添加字符 s[j],才能使得最外层形成回文。如果我们选择前者,那么需要继续考虑 s[i+1:j];如果我们选择后者,那么需要继续考虑 s[i:j-1]

因此我们可以得到如下的状态转移方程:

dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1)                     if s[i] != s[j]
dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1, dp[i + 1][j - 1])   if s[i] == s[j]

边界条件为:

dp[i][j] = 0   if i >= j

注意该动态规划为区间动态规划,需要注意 dp[i][j] 的计算顺序。一种可行的方法是,我们递增地枚举子串 s[i:j] 的长度 span = j - i + 1,再枚举起始位置 i,通过 j = i + span - 1 得到 j 的值并计算 dp[i][j]。这样的计算顺序可以保证在计算 dp[i][j] 时,状态转移方程中的状态 dp[i + 1][j]dp[i][j - 1]dp[i + 1][j - 1] 均已计算过。

[sol2-C++]
class Solution { public: int minInsertions(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n)); for (int span = 2; span <= n; ++span) { for (int i = 0; i <= n - span; ++i) { int j = i + span - 1; dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1; if (s[i] == s[j]) { dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]); } } } return dp[0][n - 1]; } };
[sol2-Python3]
class Solution: def minInsertions(self, s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] for span in range(2, n + 1): for i in range(n - span + 1): j = i + span - 1 dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1 if s[i] == s[j]: dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]) return dp[0][n - 1]

复杂度分析

  • 时间复杂度:$O(N^2)$,其中 $N$ 是字符串 s 的长度。

  • 空间复杂度:$O(N^2)$。

统计信息

通过次数 提交次数 AC比率
11383 17039 66.8%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
上一篇:
1311-获取你好友已观看的视频(Get Watched Videos by Your Friends)
下一篇:
1317-将整数转换为两个无零整数的和(Convert Integer to the Sum of Two No-Zero Integers)
本文目录
本文目录