给定字符串 str ，任务是找到要插入的最小字符数，以将其转换为回文。
null
在我们继续之前，让我们通过几个例子来理解：
- ab: 所需的插入次数为1，即。 B ab
- aa: 所需插入次数为0，即aa
- abcd: 所需插入次数为3次，即。 dcb abcd
- abcda： 所需的插入次数为2次，即a dc bcda与子字符串bcd中的插入数相同（为什么？）。
- abcde： 所需插入次数为4次，即。 edcb 憎恶
让输入字符串 str[l……h] .问题可分为三个部分：
- 找到子串str[l+1，…..h]中插入的最小数目。
- 在子字符串str[l…….h-1]中找到插入的最小数目。
- 找到子字符串str[l+1……h-1]中插入的最小数目。
递归方法 ：字符串中插入的最小数目 str[l….h] 可给出如下公式：
- 如果str[l]等于str[h]，则为minInsertions（str[l+1..h-1]）
- min（MininSections（str[l…..h-1]），MininSections（str[l+1…..h]））+1，否则
以下是上述方法的实施情况：
C++
// A Naive recursive program to find minimum // number insertions needed to make a string // palindrome #include<bits/stdc++.h> using namespace std; // Recursive function to find // minimum number of insertions int findMinInsertions( char str[], int l, int h) { // Base Cases if (l > h) return INT_MAX; if (l == h) return 0; if (l == h - 1) return (str[l] == str[h])? 0 : 1; // Check if the first and last characters are // same. On the basis of the comparison result, // decide which subproblem(s) to call return (str[l] == str[h])? findMinInsertions(str, l + 1, h - 1): (min(findMinInsertions(str, l, h - 1), findMinInsertions(str, l + 1, h)) + 1); } // Driver code int main() { char str[] = "geeks" ; cout << findMinInsertions(str, 0, strlen (str) - 1); return 0; } // This code is contributed by // Akanksha Rai |
C
// A Naive recursive program to find minimum // number insertions needed to make a string // palindrome #include <stdio.h> #include <limits.h> #include <string.h> // A utility function to find minimum of two numbers int min( int a, int b) { return a < b ? a : b; } // Recursive function to find minimum number of // insertions int findMinInsertions( char str[], int l, int h) { // Base Cases if (l > h) return INT_MAX; if (l == h) return 0; if (l == h - 1) return (str[l] == str[h])? 0 : 1; // Check if the first and last characters are // same. On the basis of the comparison result, // decide which subproblem(s) to call return (str[l] == str[h])? findMinInsertions(str, l + 1, h - 1): (min(findMinInsertions(str, l, h - 1), findMinInsertions(str, l + 1, h)) + 1); } // Driver program to test above functions int main() { char str[] = "geeks" ; printf ( "%d" , findMinInsertions(str, 0, strlen (str)-1)); return 0; } |
JAVA
// A Naive recursive Java program to find minimum // number insertions needed to make a string // palindrome class GFG { // Recursive function to find minimum number // of insertions static int findMinInsertions( char str[], int l, int h) { // Base Cases if (l > h) return Integer.MAX_VALUE; if (l == h) return 0 ; if (l == h - 1 ) return (str[l] == str[h])? 0 : 1 ; // Check if the first and last characters // are same. On the basis of the comparison // result, decide which subproblem(s) to call return (str[l] == str[h])? findMinInsertions(str, l + 1 , h - 1 ): (Integer.min(findMinInsertions(str, l, h - 1 ), findMinInsertions(str, l + 1 , h)) + 1 ); } // Driver program to test above functions public static void main(String args[]) { String str= "geeks" ; System.out.println(findMinInsertions(str.toCharArray(), 0 , str.length()- 1 )); } } // This code is contributed by Sumit Ghosh |
Python 3
# A Naive recursive program to find minimum # number insertions needed to make a string # palindrome import sys # Recursive function to find minimum # number of insertions def findMinInsertions( str , l, h): # Base Cases if (l > h): return sys.maxsize if (l = = h): return 0 if (l = = h - 1 ): return 0 if ( str [l] = = str [h]) else 1 # Check if the first and last characters are # same. On the basis of the comparison result, # decide which subproblem(s) to call if ( str [l] = = str [h]): return findMinInsertions( str , l + 1 , h - 1 ) else : return ( min (findMinInsertions( str , l, h - 1 ), findMinInsertions( str , l + 1 , h)) + 1 ) # Driver Code if __name__ = = "__main__" : str = "geeks" print (findMinInsertions( str , 0 , len ( str ) - 1 )) # This code is contributed by ita_c |
C#
// A Naive recursive C# program // to find minimum number // insertions needed to make // a string palindrome using System; class GFG { // Recursive function to // find minimum number of // insertions static int findMinInsertions( char []str, int l, int h) { // Base Cases if (l > h) return int .MaxValue; if (l == h) return 0; if (l == h - 1) return (str[l] == str[h])? 0 : 1; // Check if the first and // last characters are same. // On the basis of the // comparison result, decide // which subproblem(s) to call return (str[l] == str[h])? findMinInsertions(str, l + 1, h - 1): (Math.Min(findMinInsertions(str, l, h - 1), findMinInsertions(str, l + 1, h)) + 1); } // Driver Code public static void Main() { string str= "geeks" ; Console.WriteLine(findMinInsertions(str.ToCharArray(), 0, str.Length - 1)); } } // This code is contributed by Sam007 |
Javascript
<script> // A Naive recursive JavaScript program to find minimum // number insertions needed to make a string // palindrome // Recursive function to find minimum number // of insertions function findMinInsertions(str,l,h) { // Base Cases if (l > h) return Number.MAX_VALUE; if (l == h) return 0; if (l == h - 1) return (str[l] == str[h])? 0 : 1; // Check if the first and last characters // are same. On the basis of the comparison // result, decide which subproblem(s) to call return (str[l] == str[h]) ? findMinInsertions(str, l + 1, h - 1) : (Math.min(findMinInsertions(str, l, h - 1), findMinInsertions(str, l + 1, h)) + 1) } // Driver program to test above functions let str= "geeks" ; document.write(findMinInsertions(str,0, str.length-1)); // This code is contributed by rag2127 </script> |
输出：
3
基于动态规划的求解 如果我们仔细观察上述方法，我们会发现它 重叠子问题 . 假设我们想在字符串“abcde”中找到最小插入次数：
abcde / | / | bcde abcd bcd <- case 3 is discarded as str[l] != str[h] / | / | / | / | cde bcd cd bcd abc bc / | / | /| / | de cd d cd bc c………………….
粗体的子字符串表示递归将被终止，递归树不能从那里开始。相同颜色的子字符串表示 重叠子问题 .
如何重用子问题的解决方案？ 记忆技术用于避免类似的子问题回忆。我们可以创建一个表来存储子问题的结果，以便在再次遇到相同的子问题时可以直接使用它们。 下表表示字符串abcde的存储值。
a b c d e----------0 1 2 3 40 0 1 2 3 0 0 0 1 2 0 0 0 0 1 0 0 0 0 0
怎么填桌子？ 这张桌子应该以对角线的方式填满。对于字符串abcde，0…4，应按以下顺序填写表格：
Gap = 1: (0, 1) (1, 2) (2, 3) (3, 4)Gap = 2: (0, 2) (1, 3) (2, 4)Gap = 3: (0, 3) (1, 4)Gap = 4: (0, 4)
以下是上述方法的实施情况：
C++
// A Dynamic Programming based program to find // minimum number insertions needed to make a // string palindrome #include <bits/stdc++.h> using namespace std; // A DP function to find minimum // number of insertions int findMinInsertionsDP( char str[], int n) { // Create a table of size n*n. table[i][j] // will store minimum number of insertions // needed to convert str[i..j] to a palindrome. int table[n][n], l, h, gap; // Initialize all table entries as 0 memset (table, 0, sizeof (table)); // Fill the table for (gap = 1; gap < n; ++gap) for (l = 0, h = gap; h < n; ++l, ++h) table[l][h] = (str[l] == str[h])? table[l + 1][h - 1] : (min(table[l][h - 1], table[l + 1][h]) + 1); // Return minimum number of insertions // for str[0..n-1] return table[0][n - 1]; } // Driver Code int main() { char str[] = "geeks" ; cout << findMinInsertionsDP(str, strlen (str)); return 0; } // This is code is contributed by rathbhupendra |
C
// A Dynamic Programming based program to find // minimum number insertions needed to make a // string palindrome #include <stdio.h> #include <string.h> // A utility function to find minimum of two integers int min( int a, int b) { return a < b ? a : b; } // A DP function to find minimum number of insertions int findMinInsertionsDP( char str[], int n) { // Create a table of size n*n. table[i][j] // will store minimum number of insertions // needed to convert str[i..j] to a palindrome. int table[n][n], l, h, gap; // Initialize all table entries as 0 memset (table, 0, sizeof (table)); // Fill the table for (gap = 1; gap < n; ++gap) for (l = 0, h = gap; h < n; ++l, ++h) table[l][h] = (str[l] == str[h])? table[l+1][h-1] : (min(table[l][h-1], table[l+1][h]) + 1); // Return minimum number of insertions for // str[0..n-1] return table[0][n-1]; } // Driver program to test above function. int main() { char str[] = "geeks" ; printf ( "%d" , findMinInsertionsDP(str, strlen (str))); return 0; } |
JAVA
// A Java solution for Dynamic Programming // based program to find minimum number // insertions needed to make a string // palindrome import java.util.Arrays; class GFG { // A DP function to find minimum number // of insertions static int findMinInsertionsDP( char str[], int n) { // Create a table of size n*n. table[i][j] // will store minimum number of insertions // needed to convert str[i..j] to a palindrome. int table[][] = new int [n][n]; int l, h, gap; // Fill the table for (gap = 1 ; gap < n; ++gap) for (l = 0 , h = gap; h < n; ++l, ++h) table[l][h] = (str[l] == str[h])? table[l+ 1 ][h- 1 ] : (Integer.min(table[l][h- 1 ], table[l+ 1 ][h]) + 1 ); // Return minimum number of insertions // for str[0..n-1] return table[ 0 ][n- 1 ]; } // Driver program to test above function. public static void main(String args[]) { String str = "geeks" ; System.out.println( findMinInsertionsDP(str.toCharArray(), str.length())); } } // This code is contributed by Sumit Ghosh |
Python3
# A Dynamic Programming based program to # find minimum number insertions needed # to make a string palindrome # A utility function to find minimum # of two integers def Min (a, b): return min (a, b) # A DP function to find minimum number # of insertions def findMinInsertionsDP(str1, n): # Create a table of size n*n. table[i][j] # will store minimum number of insertions # needed to convert str1[i..j] to a palindrome. table = [[ 0 for i in range (n)] for i in range (n)] l, h, gap = 0 , 0 , 0 # Fill the table for gap in range ( 1 , n): l = 0 for h in range (gap, n): if str1[l] = = str1[h]: table[l][h] = table[l + 1 ][h - 1 ] else : table[l][h] = ( Min (table[l][h - 1 ], table[l + 1 ][h]) + 1 ) l + = 1 # Return minimum number of insertions # for str1[0..n-1] return table[ 0 ][n - 1 ]; # Driver Code str1 = "geeks" print (findMinInsertionsDP(str1, len (str1))) # This code is contributed by # Mohit kumar 29 |
C#
// A C# solution for Dynamic Programming // based program to find minimum number // insertions needed to make a string // palindrome using System; class GFG { // A DP function to find minimum number // of insertions static int findMinInsertionsDP( char []str, int n) { // Create a table of size n*n. table[i][j] // will store minimum number of insertions // needed to convert str[i..j] to a palindrome. int [,]table = new int [n, n]; int l, h, gap; // Fill the table for (gap = 1; gap < n; ++gap) for (l = 0, h = gap; h < n; ++l, ++h) table[l, h] = (str[l] == str[h])? table[l+1, h-1] : (Math.Min(table[l, h-1], table[l+1, h]) + 1); // Return minimum number of insertions // for str[0..n-1] return table[0, n-1]; } // Driver code public static void Main() { String str = "geeks" ; Console.Write( findMinInsertionsDP(str.ToCharArray(), str.Length)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // A Javascript solution for Dynamic Programming // based program to find minimum number // insertions needed to make a string // palindrome // A DP function to find minimum number // of insertions function findMinInsertionsDP(str,n) { // Create a table of size n*n. table[i][j] // will store minimum number of insertions // needed to convert str[i..j] to a palindrome. let table= new Array(n); for (let i=0;i<n;i++) { table[i]= new Array(n); } for (let i=0;i<n;i++) { for (let j=0;j<n;j++) { table[i][j]=0; } } let l=0, h=0, gap=0; // Fill the table for (gap = 1; gap < n; gap++) { for (l = 0, h = gap; h < n; l++, h++) { table[l][h] = (str[l] == str[h]) ? table[l+1][h-1] : (Math.min(table[l][h-1],table[l+1][h]) + 1); } } // Return minimum number of insertions // for str[0..n-1] return table[0][n - 1]; } // Driver program to test above function. let str = "geeks" ; document.write(findMinInsertionsDP(str, str.length)); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
3
时间复杂性： O（N^2） 辅助空间： O（N^2）
另一个动态规划解决方案（变量 最长公共子序列问题） 寻找最小插入的问题也可以通过使用 最长公共子序列（LCS）问题 .如果我们找出字符串及其反面的LCS，我们就知道一个回文最多可以包含多少个字符。我们需要插入剩下的字符。以下是步骤。
- 查找输入字符串的LCS长度及其倒数。让长度为“l”。
- 所需的最小插入次数是输入字符串的长度减去“l”。
以下是上述方法的实施情况：
C++
// An LCS based program to find minimum number // insertions needed to make a string palindrome #include <bits/stdc++.h> using namespace std; // Returns length of LCS for X[0..m-1], Y[0..n-1]. int lcs( string X, string Y, int m, int n ) { int L[m+1][n+1]; int i, j; /* Following steps build L[m+1][n+1] in bottom up fashion. Note that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for (i = 0; i <= m; i++) { for (j = 0; j <= n; j++) { if (i == 0 || j == 0) L[i][j] = 0; else if (X[i - 1] == Y[j - 1]) L[i][j] = L[i - 1][j - 1] + 1; else L[i][j] = max(L[i - 1][j], L[i][j - 1]); } } /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return L[m][n]; } void reverseStr(string& str) { int n = str.length(); // Swap character starting from two // corners for ( int i = 0; i < n / 2; i++) swap(str[i], str[n - i - 1]); } // LCS based function to find minimum number of // insertions int findMinInsertionsLCS(string str, int n) { // Creata another string to store reverse of 'str' string rev = "" ; rev = str; reverseStr(rev); // The output is length of string minus length of lcs of // str and it reverse return (n - lcs(str, rev, n, n)); } // Driver code int main() { string str = "geeks" ; cout << findMinInsertionsLCS(str, str.length()); return 0; } // This code is contributed by rathbhupendra |
C
// An LCS based program to find minimum number // insertions needed to make a string palindrome #include<stdio.h> #include <string.h> /* Utility function to get max of 2 integers */ int max( int a, int b) { return (a > b)? a : b; } /* Returns length of LCS for X[0..m-1], Y[0..n-1]. See http://goo.gl/bHQVP for details of this function */ int lcs( char *X, char *Y, int m, int n ) { int L[m+1][n+1]; int i, j; /* Following steps build L[m+1][n+1] in bottom up fashion. Note that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for (i=0; i<=m; i++) { for (j=0; j<=n; j++) { if (i == 0 || j == 0) L[i][j] = 0; else if (X[i-1] == Y[j-1]) L[i][j] = L[i-1][j-1] + 1; else L[i][j] = max(L[i-1][j], L[i][j-1]); } } /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return L[m][n]; } // LCS based function to find minimum number of // insertions int findMinInsertionsLCS( char str[], int n) { // Creata another string to store reverse of 'str' char rev[n+1]; strcpy (rev, str); strrev(rev); // The output is length of string minus length of lcs of // str and it reverse return (n - lcs(str, rev, n, n)); } // Driver program to test above functions int main() { char str[] = "geeks" ; printf ( "%d" , findMinInsertionsLCS(str, strlen (str))); return 0; } |
JAVA
// An LCS based Java program to find minimum // number insertions needed to make a string // palindrome class GFG { /* Returns length of LCS for X[0..m-1], Y[0..n-1]. See http://goo.gl/bHQVP for details of this function */ static int lcs( String X, String Y, int m, int n ) { int L[][] = new int [m+ 1 ][n+ 1 ]; int i, j; /* Following steps build L[m+1][n+1] in bottom up fashion. Note that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for (i= 0 ; i<=m; i++) { for (j= 0 ; j<=n; j++) { if (i == 0 || j == 0 ) L[i][j] = 0 ; else if (X.charAt(i- 1 ) == Y.charAt(j- 1 )) L[i][j] = L[i- 1 ][j- 1 ] + 1 ; else L[i][j] = Integer.max(L[i- 1 ][j], L[i][j- 1 ]); } } /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return L[m][n]; } // LCS based function to find minimum number // of insertions static int findMinInsertionsLCS(String str, int n) { // Using StringBuffer to reverse a String StringBuffer sb = new StringBuffer(str); sb.reverse(); String revString = sb.toString(); // The output is length of string minus // length of lcs of str and it reverse return (n - lcs(str, revString , n, n)); } // Driver program to test above functions public static void main(String args[]) { String str = "geeks" ; System.out.println( findMinInsertionsLCS(str, str.length())); } } // This code is contributed by Sumit Ghosh |
Python3
# An LCS based Python3 program to find minimum # number insertions needed to make a string # palindrome """ Returns length of LCS for X[0..m-1], Y[0..n-1]. See http://goo.gl/bHQVP for details of this function """ def lcs(X, Y, m, n) : L = [[ 0 for i in range (n + 1 )] for j in range (m + 1 )] """ Following steps build L[m + 1, n + 1] in bottom up fashion. Note that L[i, j] contains length of LCS of X[0..i - 1] and Y[0..j - 1] """ for i in range (m + 1 ) : for j in range (n + 1 ) : if (i = = 0 or j = = 0 ) : L[i][j] = 0 elif (X[i - 1 ] = = Y[j - 1 ]) : L[i][j] = L[i - 1 ][j - 1 ] + 1 else : L[i][j] = max (L[i - 1 ][j], L[i][j - 1 ]) """ L[m,n] contains length of LCS for X[0..n-1] and Y[0..m-1] """ return L[m][n] # LCS based function to find minimum number # of insertions def findMinInsertionsLCS( Str , n) : # Using charArray to reverse a String charArray = list ( Str ) charArray.reverse() revString = "".join(charArray) # The output is length of string minus # length of lcs of str and it reverse return (n - lcs( Str , revString , n, n)) # Driver code Str = "geeks" print (findMinInsertionsLCS( Str , len ( Str ))) # This code is contributed by divyehrabadiya07 |
C#
// An LCS based C# program to find minimum // number insertions needed to make a string // palindrome using System; class GFG { /* Returns length of LCS for X[0..m-1], Y[0..n-1]. See http://goo.gl/bHQVP for details of this function */ static int lcs( string X, string Y, int m, int n ) { int [,] L = new int [m + 1, n + 1]; int i, j; /* Following steps build L[m+1,n+1] in bottom up fashion. Note that L[i,j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for (i = 0; i <= m; i++) { for (j = 0; j <= n; j++) { if (i == 0 || j == 0) L[i, j] = 0; else if (X[i - 1] == Y[j - 1]) L[i, j] = L[i - 1, j - 1] + 1; else L[i, j] = Math.Max(L[i - 1, j], L[i, j - 1]); } } /* L[m,n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return L[m,n]; } // LCS based function to find minimum number // of insertions static int findMinInsertionsLCS( string str, int n) { // Using charArray to reverse a String char [] charArray = str.ToCharArray(); Array.Reverse(charArray); string revString = new string (charArray); // The output is length of string minus // length of lcs of str and it reverse return (n - lcs(str, revString , n, n)); } // Driver code static void Main() { string str = "geeks" ; Console.WriteLine(findMinInsertionsLCS(str,str.Length)); } } // This code is contributed by mits |
Javascript
<script> // An LCS based Javascript program to find minimum // number insertions needed to make a string // palindrome /* Returns length of LCS for X[0..m-1], Y[0..n-1]. See http://goo.gl/bHQVP for details of this function */ function lcs(X, Y, m, n) { let L = new Array(m+1); for (let i = 0; i < m + 1; i++) { L[i] = new Array(n+1); for (let j = 0; j < n + 1; j++) { L[i][j] = 0; } } let i, j; /* Following steps build L[m+1][n+1] in bottom up fashion. Note that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for (i = 0; i <= m; i++) { for (j = 0; j <= n; j++) { if (i == 0 || j == 0) L[i][j] = 0; else if (X[i - 1] == Y[j - 1]) L[i][j] = L[i - 1][j - 1] + 1; else L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]); } } /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return L[m][n]; } // LCS based function to find minimum number // of insertions function findMinInsertionsLCS(str, n) { let revString = str.split( '' ).reverse().join( '' ); // The output is length of string minus // length of lcs of str and it reverse return (n - lcs(str, revString , n, n)); } // Driver program to test above functions let str = "geeks" ; document.write(findMinInsertionsLCS(str, str.length)); // This code is contributed by unknown2108 </script> |
输出：
3
时间复杂性： O（N^2） 辅助空间 ：O（N^2）
相关文章： 使字符串回文化所需的最小追加数 本文由 阿希什·巴恩瓦尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
