使字符串回文化所需的最小追加数

给定一个字符串s,我们需要告诉最少要追加的字符(在末尾插入),以使字符串具有回文性。

null

例如:

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主页上,并帮助其他极客。 如果您发现任何不正确的地方,或者您想分享有关上述主题的更多信息,请写下评论。

© 版权声明
THE END
喜欢就支持一下吧
点赞13 分享