给定一个字符串s,我们需要告诉最少要追加的字符(在末尾插入),以使字符串具有回文性。
例如:
Input : s = "abede"Output : 2We can make string palindrome as "abedeba"by adding ba at the end of the string.Input : s = "aabb"Output : 2We can make string palindrome as"aabbaa"by adding aa at the end of the string.
解决方法是逐个删除字符串开头的字符,并检查字符串是否为回文。 例如,考虑上面的字符串,s= “阿贝德” . 我们检查字符串是否为回文。 结果为false,然后我们从字符串的开头删除字符,现在字符串变为 “贝德” . 我们检查字符串是否为回文。结果再次为false,然后我们从字符串的开头删除字符,现在字符串变为false “爱德” . 我们检查字符串是否为回文。结果为true,因此输出变为2,即从字符串中删除的字符数。
C++
// C program to find minimum number of appends // needed to make a string Palindrome #include<stdio.h> #include<string.h> #include<stdbool.h> // Checking if the string is palindrome or not bool isPalindrome( char *str) { int len = strlen (str); // single character is always palindrome if (len == 1) return true ; // pointing to first character char *ptr1 = str; // pointing to last character char *ptr2 = str+len-1; while (ptr2 > ptr1) { if (*ptr1 != *ptr2) return false ; ptr1++; ptr2--; } return true ; } // Recursive function to count number of appends int noOfAppends( char s[]) { if (isPalindrome(s)) return 0; // Removing first character of string by // incrementing base address pointer. s++; return 1 + noOfAppends(s); } // Driver program to test above functions int main() { char s[] = "abede" ; printf ( "%d" , noOfAppends(s)); return 0; } |
JAVA
// Java program to find minimum number of appends // needed to make a string Palindrome class GFG { // Checking if the string is palindrome or not static boolean isPalindrome( char []str) { int len = str.length; // single character is always palindrome if (len == 1 ) return true ; // pointing to first character int ptr1 = 0 ; // pointing to last character int ptr2 = len- 1 ; while (ptr2 >= ptr1) { if (str[ptr1] != str[ptr2]) return false ; ptr1++; ptr2--; } return true ; } // Recursive function to count number of appends static int noOfAppends(String s) { if (isPalindrome(s.toCharArray())) return 0 ; // Removing first character of string by // incrementing base address pointer. s=s.substring( 1 ); return 1 + noOfAppends(s); } // Driver code public static void main(String arr[]) { String s = "abede" ; System.out.printf( "%d" , noOfAppends(s)); } } // This code contributed by Rajput-Ji |
Python3
# Python3 program to find minimum number of appends # needed to make a String Palindrome # Checking if the String is palindrome or not def isPalindrome( Str ): Len = len ( Str ) # single character is always palindrome if ( Len = = 1 ): return True # pointing to first character ptr1 = 0 # pointing to last character ptr2 = Len - 1 while (ptr2 > ptr1): if ( Str [ptr1] ! = Str [ptr2]): return False ptr1 + = 1 ptr2 - = 1 return True # Recursive function to count number of appends def noOfAppends(s): if (isPalindrome(s)): return 0 # Removing first character of String by # incrementing base address pointer. del s[ 0 ] return 1 + noOfAppends(s) # Driver Code se = "abede" s = [i for i in se] print (noOfAppends(s)) # This code is contributed by Mohit Kumar |
C#
// C# program to find minimum number of appends // needed to make a string Palindrome using System; class GFG { // Checking if the string is palindrome or not static Boolean isPalindrome( char []str) { int len = str.Length; // single character is always palindrome if (len == 1) return true ; // pointing to first character char ptr1 = str[0]; // pointing to last character char ptr2 = str[len-1]; while (ptr2 > ptr1) { if (ptr1 != ptr2) return false ; ptr1++; ptr2--; } return true ; } // Recursive function to count number of appends static int noOfAppends(String s) { if (isPalindrome(s.ToCharArray())) return 0; // Removing first character of string by // incrementing base address pointer. s=s.Substring(1); return 1 + noOfAppends(s); } // Driver code public static void Main(String []arr) { String s = "abede" ; Console.Write( "{0}" , noOfAppends(s)); } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find minimum number of appends // needed to make a string Palindrome // Checking if the string is palindrome or not function isPalindrome(str) { let len = str.length; // single character is always palindrome if (len == 1) return true ; // pointing to first character let ptr1 = 0; // pointing to last character let ptr2 = len-1; while (ptr2 >= ptr1) { if (str[ptr1] != str[ptr2]) return false ; ptr1++; ptr2--; } return true ; } // Recursive function to count number of appends function noOfAppends(s) { if (isPalindrome(s.split( "" ))) return 0; // Removing first character of string by // incrementing base address pointer. s=s.substring(1); return 1 + noOfAppends(s); } // Driver code let s = "abede" ; document.write(noOfAppends(s)); // This code is contributed by unknown2108 </script> |
2
描述了上述方法和O(n**2)方法。
有效方法:
我们也有一个算法,利用 Knuth-Morris-Pratt算法 这就是O(n)时间复杂度。
该方法背后的基本思想是,我们计算从末尾算起的最大子字符串,字符串的长度减去该值就是最小的附加数。逻辑是直观的,我们不需要附加回文,只需要那些不构成回文的。为了从末尾找到这个最大的回文,我们反转字符串,计算DFA,然后再次反转字符串(从而获得原始字符串),并找到最终状态,它表示字符串与受尊敬的字符串的匹配数,因此我们在O(n)时间内得到从末尾返回的最大子字符串。
以下是上述方法的实施情况:
C++
// CPP program for above approach #include <algorithm> #include <iostream> #include <string> using namespace std; // This class builds the dfa and // precomputes the state. // See KMP algorithm for explanation class kmp_numeric { private : int n; int ** dfa; public : kmp_numeric(string& s) { n = s.length(); int c = 256; // Create dfa dfa = new int *[n]; // Iterate from 0 to n for ( int i = 0; i < n; i++) dfa[i] = new int ; int x = 0; // Iterate from 0 to n for ( int i = 0; i < c; i++) dfa[0][i] = 0; // Initialise dfa[0][s[0]] = 1 dfa[0][s[0]] = 1; // Iterate i from 1 to n-1 for ( int i = 1; i < n; i++) { // Iterate j from 0 to c - 1 for ( int j = 0; j < c; j++) { dfa[i][j] = dfa[x][j]; } dfa[i][s[i]] = i + 1; x = dfa[x][s[i]]; } } // This function finds the overlap // between two strings,by // changing the state. int longest_overlap(string& query) { // q1 is length of query int ql = query.length(); int state = 0; // Iterate from 0 to q1 - 1 for ( int i = 0; i < ql; i++) { state = dfa[state][query[i]]; } return state; } }; int min_appends(string& s) { // Reverse the string. reverse(s.begin(), s.end()); // Build the DFA for the // reversed String kmp_numeric kmp = s; // Get the original string back reverse(s.begin(), s.end()); // Largest overlap in this case is the // largest string from the end which // is a palindrome. int ans = s.length() - kmp.longest_overlap(s); return ans; } // Driver Code int main() { string s = "deep" ; // Answer : 3 string t = "sososososos" ; // Answer : 0 cout << min_appends(s) << endl; cout << min_appends(t) << endl; } |
30
建议人: 普拉蒂克·普里亚达桑
相关文章: 动态规划|集28(形成回文的最小插入次数) 本文由 舒巴姆·乔杜里 .如果你喜欢GeekSforgek,并想贡献自己的力量,你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上,并帮助其他极客。 如果您发现任何不正确的地方,或者您想分享有关上述主题的更多信息,请写下评论。