形成回文所需的最少插入次数

什么是回文串？

如果一个字符串从后向前读和从前向后读的结果是一样的，那么这个字符串就称为回文串。

回文串的反转与其自身相同。

例如

"abcddbca"、"abcdbca" 都是回文串的例子。

问题陈述

在这里，我们给定一个输入字符串，我们必须返回在给定字符串的任意位置插入最少数量的字符，使得该字符串变成一个回文串。

例如

字符串为 "abcd"，我们需要插入三个字符来构成一个回文串。

结果字符串将是 "abcdcba"。如果字符串是 "abcba"，我们将需要 0 次插入，因为它已经是一个回文串。

方法 1

我们将使用递归方法来解决这个问题。我们的任务是确定字符串所需的最小插入次数，该字符串的定义范围是从 索引 0 到索引 n-1，其中 n 是字符串的长度。

所以字符串将表示为 str[low, hi]

有两种情况

情况 1: 如果 str[low]==str[hi]，那么我们将从 str[low+1,hi-1] 中获得答案

情况 2: 否则，我们将得到的答案是 最小值(str[low,hi-1], str[low+1,hi]) + 1。

Java 代码

输出

说明

在上面的代码中，我们有一个字符串 "abcdba"，它不是一个回文串。我们只需要插入一个字符 'c' 就能使其成为回文串。

结果字符串是 "abcdcba"，它是一个回文串。

上述代码的时间复杂度是 O(nⁿ)，这是指数级的。

空间复杂度: O(n) 用于递归栈空间。

方法 2

上述递归代码存在重叠子问题，因此我们可以使用动态规划方法来优化任何具有重叠子问题的递归问题。

我们将使用记忆化技术（这是一种编程中的优化技术，可以使应用程序更高效、从而更快）来解决问题。在记忆化中，我们会将每次递归调用的结果存储到一个数组中，这样下次就不需要再次计算了。

Java 代码

输出

说明

在上面的代码中，我们有一个字符串 "abcdca"，它需要字符 'b' 才能成为回文串。所以，答案是一，我们使用一个 n x n 的二维数组来存储每次递归调用的结果。

时间复杂度: O(n²)

空间复杂度: O(n²)+递归栈空间

我们可以进一步优化它，不使用递归。我们可以使用制表法，并避免递归所使用的额外空间。

方法 3

我们将使用一个二维数组，其中 dp[i][j] 将存储将字符串从第 i^th 个索引到第 j^th 个索引的部分变成回文串所需的最小字符数。

我们将使用“间距”法，其中间距从 0 开始到 n-1，我们将按间距的方式填充表格。

Java 代码

输出

在上面的代码中，我们有一个字符串 "abcdef"，它至少需要五个字符才能形成一个回文串，即 "abcdefedcba"。

时间复杂度: O(n²)

空间复杂度: O(n²)

方法 4

这是解决此问题的最流行的方法之一。

如果我们得到给定字符串的最长回文子序列的长度，那么剩余字符的数量就是我们的答案。

如果我们求出该字符串与其反转字符串的最长公共子序列，那么它将返回最长回文子序列的长度。

设 L 是最长回文子序列的长度，那么 n-L 就是答案。

例如

Java 代码

输出

说明

我们找到字符串及其反转字符串的最长公共子序列，然后得到我们的结果值。

时间复杂度： O(n2)

空间复杂度: O(n2)