Java 中形成回文的最小插入数

2024年9月10日 | 阅读 9 分钟

给定一个字符串。我们的任务是通过插入字符来将该字符串转换为回文串。字符只能插入到输入字符串的最左侧。在输出中，我们需要提及为了使输入字符串成为回文串而插入的字符总数。请参阅以下示例。

示例：1

输入

字符串 str = "ab"

输出 1

解释： 如果我们在字符串的最左侧插入字符 'b'，我们得到字符串 "bab"，这是一个回文串。因此，插入到输入字符串中的字符总数为 1。

示例：2

输入

字符串 str = "abcd"

输出 3

解释： 如果我们在字符串的最左侧插入字符 'b'，我们得到字符串 "dcbabcd"，这是一个回文串。因此，插入到输入字符串中的字符总数为 3。

例如：3

输入

字符串 str = "bab"

输出 0

解释： 输入字符串已经是回文串。因此，不需要插入任何字符。输出为 0。

朴素方法

在这种方法中，我们将使用递归。我们将使用一个名为 computeMinInsertions() 的方法来计算使字符串成为回文串所需的最小字符数。请观察以下实现。

文件名： MinInsertionPalindrome.java

public class MinInsertionPalindrome 
{

// Recursive method that computes the minimum number
// of characters insertion to make the string inputStr a palindrome 
public int computeMinInsertions(char inputStr[], int s, int e)
{
// Handling the Base Cases
if (s > e) 
{
return Integer.MAX_VALUE;
}
if (s == e) 
{
// the input string only contains one character
return 0;
}
if (s == e - 1) 
{
// the input string only contains two characters
// if both the characters are the same, the string is a palindrome.
// Otherwise, we need to add one more character at the beginning of
// the input string.
return (inputStr[s] == inputStr[e]) ? 0 : 1;
}

// Checking whether the first and the last characters
// are the same or not. The comparison result decides which 
// subproblems we need to solve.

if(inputStr[s] == inputStr[e]) 
{
// the first and the last characters match. Hence, we exclude the 
// first and the last characters and apply the recursion on the 
// rest of the characters of the string
return computeMinInsertions(inputStr, s + 1, e - 1);
}
else
{
// computing minimum of the two subproblems: one subproblem is excluding the first character, and 
// other subproblem is excluding the last character.
return (Integer.min(computeMinInsertions(inputStr, s, e - 1), computeMinInsertions(inputStr, s + 1, e)) + 1);
}
}

// Main Method
public static void main(String argvs[])
{
// creating an object of the class MinInsertionPalindrome
MinInsertionPalindrome obj = new MinInsertionPalindrome();

// input 1
String inputStr= "ab";
int ans = obj.computeMinInsertions(inputStr.toCharArray(), 0, inputStr.length() - 1);
System.out.println("For the string: " + inputStr);
System.out.println("The minimum number of characters that should be inserted to make it palindromic is: " + ans);
System.out.println();

// input 2
inputStr= "abcd";
ans = obj.computeMinInsertions(inputStr.toCharArray(), 0, inputStr.length() - 1);
System.out.println("For the string: " + inputStr);
System.out.println("The minimum number of characters that should be inserted to make it palindromic is: " + ans);
System.out.println();

// input 3
inputStr= "bab";
ans = obj.computeMinInsertions(inputStr.toCharArray(), 0, inputStr.length() - 1);
System.out.println("For the string: " + inputStr);
System.out.println("The minimum number of characters that should be inserted to make it palindromic is: " + ans);
System.out.println();
}
}

输出

For the string: ab
The minimum number of characters that should be inserted to make it palindromic is: 1

For the string: abcd
The minimum number of characters that should be inserted to make it palindromic is: 3

For the string: bab
The minimum number of characters that should be inserted to make it palindromic is: 0

复杂度分析： 程序的时间复杂度为 O(nⁿ)，空间复杂度为 O(n)，其中 n 是输入字符串中存在的字符总数。

上述程序的时间复杂度非常高，不适用于大型输入。高时间复杂度的原因是许多子问题被反复计算。我们可以通过动态规划来避免子问题的重复计算。以下方法展示了这一点。

方法：使用动态规划

我们将使用一个二维数组来存储子问题的解，以便它们不会被重复计算。此外，我们将使用存储的子问题解来计算最终解。

文件名： MinInsertionPalindrome1.java

public class MinInsertionPalindrome1  
{

// Recursive method that computes the minimum number
// of characters insertion to make the string inputStr a palindrome 
public int computeMinInsertions(char inputStr[], int len)
{
// Creating a (len x len) sized table. dp[p][q]
// stores the minimum number of insertions that are 
// required for converting the string[p ... q] into a palindrome
int dp[][] = new int[len][len];
int l, h, gap;

// Filling the dp table
for (int gp = 1; gp < len; gp++)
{
for (l = 0, h = gp; h < len; l++, h++)
{
dp[l][h] = (inputStr[l] == inputStr[h]) ? dp[l + 1][h - 1] : (Integer.min(dp[l][h - 1], dp[l + 1][h]) + 1);
}
}

// Returning the minimum number of insertions
// for the str[0 ... len - 1]
return dp[0][len - 1];
}

// Main Method
public static void main(String argvs[])
{
// creating an object of the class MinInsertionPalindrome1
MinInsertionPalindrome1 obj = new MinInsertionPalindrome1();

// input 1
String inputStr= "ab";
int ans = obj.computeMinInsertions(inputStr.toCharArray(), inputStr.length());
System.out.println("For the string: " + inputStr);
System.out.println("The minimum number of characters that should be inserted to make it palindromic is: " + ans);
System.out.println();

// input 2
inputStr= "abcd";
ans = obj.computeMinInsertions(inputStr.toCharArray(), inputStr.length());
System.out.println("For the string: " + inputStr);
System.out.println("The minimum number of characters that should be inserted to make it palindromic is: " + ans);
System.out.println();

// input 3
inputStr= "bab";
ans = obj.computeMinInsertions(inputStr.toCharArray(), inputStr.length());
System.out.println("For the string: " + inputStr);
System.out.println("The minimum number of characters that should be inserted to make it palindromic is: " + ans);
System.out.println();
}
}

输出

For the string: ab
The minimum number of characters that should be inserted to make it palindromic is: 1

For the string: abcd
The minimum number of characters that should be inserted to make it palindromic is: 3

For the string: bab
The minimum number of characters that should be inserted to make it palindromic is: 0

复杂度分析： 由于使用了两个循环（嵌套循环），程序的总时间复杂度为 O(n²)。此外，在 computeMinInsertions() 方法中使用了二维数组，使得程序的空间复杂度为 O(n²)，其中 n 是输入字符串中存在的字符总数。

另一种方法：使用最长公共子序列

另一种方法是使用 LCS（最长公共子序列）问题的概念。使用此方法，我们将找到输入字符串及其反序字符串的最长公共子序列。

文件名： MinInsertionPalindrome2.java

public class MinInsertionPalindrome2  
{

public int findLCS( String st1, String st2, int siz1, int siz2)
{
int LCS[][] = new int[siz1 + 1][siz2 + 1];
int p, q;

// Following are the steps used to fill LCS[siz1 + 1][siz2 + 1] in
// the bottom-up fashion. Note that LCS[p][q]
// contains length of LCS of st1[0 ... p - 1]
// and st2[0 ... q - 1] 
for (p = 0; p <= siz1; p++)
{
for (q = 0; q <= siz2; q++)
{
if (p == 0 || q == 0)
{
LCS[p][q] = 0;
}

else if (st1.charAt(p - 1) == st2.charAt(q - 1))
{
LCS[p][q] = LCS[p - 1][q - 1] + 1;
}

else
{
LCS[p][q] = Integer.max(LCS[p - 1][q], LCS[p][q - 1]);
}
}
}

// LCS[siz1][siz2] keeps the length of the LCS for
//   st1[0 ...  siz1 - 1] and st2[0 ... siz2 - 1] 
return LCS[siz1][siz2];
}

// A method that computes the minimum number
// of characters insertion to make the string inputStr a palindrome 
public int computeMinInsertions(String inputStr, int len)
{
// Using StringBuffer to reverse a String
StringBuffer strBufObj = new StringBuffer(inputStr);
strBufObj.reverse();
String reverseString = strBufObj.toString();

// The result is the length of the input string minus
// the length of the LCS of the input string and its reverse

int res = len - findLCS(inputStr, reverseString , len, len);
return res;
}

// Main Method
public static void main(String argvs[])
{
// creating an object of the class MinInsertionPalindrome2
MinInsertionPalindrome2 obj = new MinInsertionPalindrome2();

// input 1
String inputStr= "ab";
int ans = obj.computeMinInsertions(inputStr, inputStr.length());
System.out.println("For the string: " + inputStr);
System.out.println("The minimum number of characters that should be inserted to make it palindromic is: " + ans);
System.out.println();

// input 2
inputStr= "abcd";
ans = obj.computeMinInsertions(inputStr, inputStr.length());
System.out.println("For the string: " + inputStr);
System.out.println("The minimum number of characters that should be inserted to make it palindromic is: " + ans);
System.out.println();

// input 3
inputStr= "bab";
ans = obj.computeMinInsertions(inputStr, inputStr.length());
System.out.println("For the string: " + inputStr);
System.out.println("The minimum number of characters that should be inserted to make it palindromic is: " + ans);
System.out.println();
}
}

输出

For the string: ab
The minimum number of characters that should be inserted to make it palindromic is: 1

For the string: abcd
The minimum number of characters that should be inserted to make it palindromic is: 3

For the string: bab
The minimum number of characters that should be inserted to make it palindromic is: 0

复杂度分析：该程序的时间复杂度和空间复杂度与前一个程序相同。

我们仍然可以对空间复杂度进行优化。请注意，在 LCS 表中，我们只需要当前行和上一行的元素。其说明在以下程序中给出。

文件名： MinInsertionPalindrome3.java

public class MinInsertionPalindrome3  
{

public int findLCS( String st1, String st2, int siz1, int siz2)
{
// for storing the values of the last computed elements
int prvArr[] = new int[siz1 + 1];

// for storing the values of the currently computed elements
int currArr[] = new int[siz2 + 1];

int p, q;

for (p = 0; p <= siz1; p++)
{
for (q = 0; q <= siz2; q++)
{
// handling the base case
if (p == 0 || q == 0)
{
prvArr[q] = 0;
}

// if the first element of the input string and its reverse are the same
// then increment the value of the currArr[q] by 1
else if (st1.charAt(p - 1) == st2.charAt(q - 1))
{
currArr[q] = prvArr[q - 1] + 1;
}

else
{
currArr[q] = Math.max(prvArr[q], currArr[q - 1]);
}
}

for (int p1 = 0; p1 <= siz1; p1++)
{
prvArr[p1] = currArr[p1];
}

}

// LCS[siz1][siz2] keeps the length of the LCS for
//   st1[0 ...  siz1 - 1] and st2[0 ... siz2 - 1] 
return prvArr[siz1];
}

// A method that computes the minimum number
// of characters insertion to make the string inputStr a palindrome 
public int computeMinInsertions(String inputStr, int len)
{
// Using StringBuffer to reverse a String
StringBuffer strBufObj = new StringBuffer(inputStr);
strBufObj.reverse();
String reverseString = strBufObj.toString();

// The result is the length of the input string minus
// the length of the LCS of the input string and its reverse

int res = len - findLCS(inputStr, reverseString , len, len);
return res;
}

// Main Method
public static void main(String argvs[])
{
// creating an object of the class MinInsertionPalindrome3
MinInsertionPalindrome3 obj = new MinInsertionPalindrome3();

// input 1
String inputStr= "ab";
int ans = obj.computeMinInsertions(inputStr, inputStr.length());
System.out.println("For the string: " + inputStr);
System.out.println("The minimum number of characters that should be inserted to make it palindromic is: " + ans);
System.out.println();

// input 2
inputStr= "abcd";
ans = obj.computeMinInsertions(inputStr, inputStr.length());
System.out.println("For the string: " + inputStr);
System.out.println("The minimum number of characters that should be inserted to make it palindromic is: " + ans );
System.out.println();

// input 3
inputStr= "bab";
ans = obj.computeMinInsertions(inputStr, inputStr.length());
System.out.println("For the string: " + inputStr );
System.out.println("The minimum number of characters that should be inserted to make it palindromic is: " + ans );
System.out.println();
}
}

输出

For the string: ab
The minimum number of characters that should be inserted to make it palindromic is: 1

For the string: abcd
The minimum number of characters that should be inserted to make it palindromic is: 3

For the string: bab
The minimum number of characters that should be inserted to make it palindromic is: 0

复杂度分析： 该程序的时间复杂度与前一个程序相同。然而，该程序使用的空间复杂度比前一个程序要好，即 O(N)，其中 N 是输入字符串中存在的字符总数。这是因为该程序仅使用了单维数组。

下一个主题Java 中的摆动排序

Java 中形成回文的最小插入数

朴素方法

方法：使用动态规划

另一种方法：使用最长公共子序列

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中形成回文的最小插入数

朴素方法

方法：使用动态规划

另一种方法：使用最长公共子序列

相关帖子

Java 中的单词阶梯问题

Java 中的下一个更大元素

Java 游戏

Java 中的稀疏数

Java 中的 Bully 算法

Change Gregorian Calendar to SimpleDateFormat in Java

CharsetDecoder detectedCharset() method in Java with Examples

Java 中不使用除法（/）运算符进行除法

Java 中使用 == 和 .equals() 方法比较 String 的区别

如何在 Java 中创建抽象类的实例

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器