下一个→ ←上一页

最少的插入以形成回文

什么是回文?

如果从向后和向前两个方向读取一个字符串，则该字符串称为回文字符串。

回文字符串的反向与字符串相同。

例如:

"abcddbca"， "abcdbca"是回文字符串的一个例子。

问题陈述:

在这里，我们得到一个输入字符串，我们必须返回在给定字符串的任何位置插入的最小字符数，以便给定字符串成为回文字符串。

例如:

字符串是"abcd"，我们需要三次插入来形成回文字符串。

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

方法1

我们将使用递归方法来解决这个问题。方法中定义的字符串的最小插入数索引0到索引n-1在哪里n是弦的长度。

字符串将被表示为str(低,嗨)

有两种情况:

案例1如果str[low]==str[hi]则我们将从str[low +1,hi-1]得到答案

案例2:否则我们将得到的答案为Minimum(str[low,hi-1]，str[low+1,hi])+1。

Java代码:

            类HelloWorld{公共静态void main(String[] args) {String str="abcdba";int ans = getMinInsertion (str 0 str.length () 1);System.out.println (ans);}公共静态int getmininsert (String str,int low,int hi){if(low==hi)返回0;如果(str.charAt(低)= = str.charAt(你好))返回getMinInsertion (str,低+ 1,hi-1);else {int result1= getmininsert (str,low+1,hi);int result2 = getMinInsertion (str,低,hi-1);返回Math.min (result1,编写此表达式result2) + 1;}}}
           

输出:

解释

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

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

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

空间复杂度：O (n)对于递归堆栈空间。

方法2

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

我们将使用记忆技术(这是编程中的一种优化技术，使应用程序更高效，从而更快)来解决这个问题。在记忆法中，我们将每次递归调用的结果存储到数组中，因此下次不再进行计算。

Java代码:

            进口java.util。*;类HelloWorld{公共静态void main(String[] args) {String str="abcdca";int n = str.length ();int [] [] dp = new int [n] [n];(int i = 0;我< dp.length; + +) {(int j = 0; < dp [0] . length; j + +) {dp[我][j] = 1;}} int ans= getmininsert (str,0,n-1,dp);System.out.println (dp [0] [n]);} public static int getmininsert (String str,int low,int hi,int[][] dp){if(low==hi) return dp[low][hi]=0;如果(dp(低)(你好)! = 1)返回dp(低)(你好);如果(str.charAt(低)= = str.charAt(你好))返回dp(低)[嗨]= getMinInsertion (str,低+ 1,hi-1 dp); else { int result1=getMinInsertion(str,low+1,hi,dp); int result2=getMinInsertion(str,low,hi-1,dp); return dp[low][hi]=Math.min(result1,result2)+1; } } }
           

输出:

解释

在上面的代码中，我们有一个名为"abcdca"的字符串，它需要字符'b'使自己成为回文。所以，答案是1，我们使用一个2d数组nxn来存储每次递归调用的结果。

时间复杂度:O (n²）

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

我们可以在不使用递归的情况下进一步优化它。我们可以使用表格法来避免递归所占用的额外空间。

方法3

我们将使用2D数组，其中dp[i][j]将存储从i生成一个回文字符串所需的最小字符^thj的索引^th索引。

我们将使用空白方法，其中空白将从0开始到n-1，我们将按空白填充表。

Java代码:

            进口java.util。*;类HelloWorld {public static void main(String[] args) {String str="abcdef";int n = str.length ();int [] [] dp = new int [n] [n];(int差距= 0;差距< n; + +){差距(int = 0开始,结束=差距;< n; + +, + +){如果(差距= = 0)dp[开始][结束]= 0;else if(差距= = 1)dp[开始][结束]= str.charAt (start) = = str.charAt(结束)? 0:1;else {if(str.charAt(start)==str.charAt(end)) dp[start][end]=dp[start+1][end-1];其他dp[开始][结束]= 1 + Math.min (dp[开始][end-1], dp[开始+ 1][结束]);}}} System.out.println(dp[0][n-1]);}}
           

输出:

在上面的代码中，我们有一个名为“abcdef”的字符串，它至少需要5个字符才能形成一个名为“abcdefdcba”的回文字符串。

时间复杂度:O (n²）

空间复杂度:O (n²）

方法4

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

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

如果我们得到字符串的最长公共子序列和它的反向字符串，那么它将返回最长回文子序列的长度。

设L为最长回文子序列长度，则n-L为答案。

例如:

Java代码:

            进口java.util。*;类HelloWorld{公共静态void main(String[] args) {String str="abcd";int n = str.length ();int L = getLCS (str,逆向(str));System.out.println (n-L);} public static String reverse(String str){String ans="";(int i = str.length() 1;我> = 0;我——){char ch = str.charAt(我);ans + = ch;}返回答;} public static int getLCS(String s1,String s2){int n=s1.length(); int m=s2.length(); int[][] dp=new int[n+1][m+1]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s1.charAt(i-1)==s2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]); } } return dp[n][m]; } }
           

输出: