给定一个字符串，找出最少需要多少个字符，使得该单词成为回文。 例如：
ABBA：0（已经是回文） ABB：1 FAE：2 FOO：1
10个回答
48
由于这可能是一份作业，所以只提供算法。您需要找到字符串末尾的最长回文子串。可以通过创建一个算法来判断一个字符串是否为回文，方法是从字符串的开头和结尾分别运行两个指针，并检查它们所引用的字符是否相同，直到它们在中间相遇。类似这样：
function isPalindrome(s):
i1 = 0
i2 = s.length() - 1
while i2 > i1:
if s.char_at(i1) not equal to s.char_at(i2):
return false
increment i1
decrement i2
return true
使用完整字符串进行尝试。如果不起作用，则将第一个字符保存在堆栈上，然后查看剩余的字符是否形成回文。如果这样不起作用，则也保存第二个字符，并从第三个字符开始再次检查。
最终您将得到一系列已保存的字符和其余的回文字符串。
最好的情况是原始字符串本来就是回文的，在这种情况下，堆栈将为空。最糟糕的情况是只剩下一个字符（一个单字符字符串自动是回文），其他所有字符都在堆栈中。
您需要添加到原始字符串末尾的字符数等于堆栈中的字符数。
要实际制作回文，逐个弹出堆栈上的字符，并将它们放在回文字符串的开头和结尾。
示例：
String Palindrome Stack Notes
------ ---------- ----- -----
ABBA Y - no characters needed.
String Palindrome Stack Notes
------ ---------- ----- -----
ABB N -
BB Y A one character needed.
ABBA Y - start popping, finished.
String Palindrome Stack Notes
------ ---------- ----- -----
FAE N -
AE N F
E Y AF two characters needed.
AEA Y F start popping.
FAEAF Y - finished.
String Palindrome Stack Notes
------ ---------- ----- -----
FOO N -
OO Y F one character needed.
FOOF Y - start popping, finished.
String Palindrome Stack Notes
------ ---------- ----- -----
HAVANNA N -
AVANNA N H
VANNA N AH
ANNA Y VAH three characters needed.
VANNAV Y AH start popping.
AVANNAVA Y H
HAVANNAVAH Y - finished.
String Palindrome Stack Notes
------ ---------- -------- -----
deoxyribo N -
eoxyribo N d
oxyribo N ed
: : :
bo N iryxoed
o Y biryxoed eight chars needed.
bob Y iryxoed start popping.
ibobi Y ryxoed
: : :
oxyribobiryxo Y ed
eoxyribobiryxoe Y d
deoxyribobiryxoed Y - finished.
将这个方法转换为“代码”：
function evalString(s):
stack = ""
while not isPalindrome(s):
stack = s.char_at(0) + stack
s = s.substring(1)
print "Need " + s.length() + " character(s) to make palindrome."
while stack not equal to "":
s = stack.char_at(0) + s + stack.char_at(0)
stack = stack.substring(1)
print "Palindrome is " + s + "."
对于那些不太关心伪代码的人，这里有一个用C语言编写的测试程序可以实现同样的功能。
#include <stdio.h>
#include <string.h>
static char *chkMem (char *chkStr) {
if (chkStr == NULL) {
fprintf (stderr, "Out of memory.\n");
exit (1);
}
return chkStr;
}
static char *makeStr (char *oldStr) {
char *newStr = chkMem (malloc (strlen (oldStr) + 1));
return strcpy (newStr, oldStr);
}
static char *stripFirst (char *oldStr) {
char *newStr = chkMem (malloc (strlen (oldStr)));
strcpy (newStr, &(oldStr[1]));
free (oldStr);
return newStr;
}
static char *addFront (char *oldStr, char addChr) {
char *newStr = chkMem (malloc (strlen (oldStr) + 2));
sprintf (newStr, "%c%s", addChr, oldStr);
free (oldStr);
return newStr;
}
static char *addBoth (char *oldStr, char addChr) {
char *newStr = chkMem (malloc (strlen (oldStr) + 3));
sprintf (newStr, "%c%s%c", addChr, oldStr, addChr);
free (oldStr);
return newStr;
}
static int isPalindrome (char *chkStr) {
int i1 = 0;
int i2 = strlen (chkStr) - 1;
while (i2 > i1)
if (chkStr[i1++] != chkStr[i2--])
return 0;
return 1;
}
static void evalString (char *chkStr) {
char * stack = makeStr ("");
char * word = makeStr (chkStr);
while (!isPalindrome (word)) {
printf ("%s: no, ", word);
stack = addFront (stack, *word);
word = stripFirst (word);
printf ("stack <- %s, word <- %s\n", stack, word);
}
printf ("%s: yes, need %d character(s)\n", word, strlen (stack));
printf ("----------------------------------------\n");
printf ("Adjusting to make palindrome:\n");
while (strlen (stack) > 0) {
printf (" %s, stack <- %s\n", word, stack);
word = addBoth (word, *stack);
stack = stripFirst (stack);
}
printf (" %s\n", word);
printf ("========================================\n");
free (word);
free (stack);
}
int main (int argc, char *argv[]) {
int i;
for (i = 1; i < argc; i++) evalString (argv[i]);
return 0;
}
使用以下方式运行：
mkpalin abb abba fae foo deoxyribo
输出：
abb: no, stack <- a, word <- bb
bb: yes, need 1 character(s)
----------------------------------------
Adjusting to make palindrome:
bb, stack <- a
abba
========================================
abba: yes, need 0 character(s)
----------------------------------------
Adjusting to make palindrome:
abba
========================================
fae: no, stack <- f, word <- ae
ae: no, stack <- af, word <- e
e: yes, need 2 character(s)
----------------------------------------
Adjusting to make palindrome:
e, stack <- af
aea, stack <- f
faeaf
========================================
foo: no, stack <- f, word <- oo
oo: yes, need 1 character(s)
----------------------------------------
Adjusting to make palindrome:
oo, stack <- f
foof
========================================
deoxyribo: no, stack <- d, word <- eoxyribo
eoxyribo: no, stack <- ed, word <- oxyribo
oxyribo: no, stack <- oed, word <- xyribo
xyribo: no, stack <- xoed, word <- yribo
yribo: no, stack <- yxoed, word <- ribo
ribo: no, stack <- ryxoed, word <- ibo
ibo: no, stack <- iryxoed, word <- bo
bo: no, stack <- biryxoed, word <- o
o: yes, need 8 character(s)
----------------------------------------
Adjusting to make palindrome:
o, stack <- biryxoed
bob, stack <- iryxoed
ibobi, stack <- ryxoed
ribobir, stack <- yxoed
yribobiry, stack <- xoed
xyribobiryx, stack <- oed
oxyribobiryxo, stack <- ed
eoxyribobiryxoe, stack <- d
deoxyribobiryxoed
========================================
- paxdiablo
2
我曾在一次比赛中看到这个问题，当时我很困惑。
但是经过和朋友们的讨论，我认为找到需要插入字符串的最小字符数，需要找到以其为中心的最长回文串。
以字符串 "accaz" 为例
将字符串 accaz 想象成在 acca 后面插入 z 得到的回文串。因此我们需要在开头再添加一个 z。
另一个字符串："mykma"
将其想象成 mym 中插入两个字符 k 和 a 得到的回文串。因此我们需要再添加两个字符才能使它成为回文串。（回文串应该是 amkykma）。
我已经用 Java 编写了一个实现此功能的程序。
import java.util.*;
import java.io.*;
public class MinPalin{
//Function to check if a string is palindrome
public boolean isPaindrome(String s){
int beg=0;
int end=s.length()-1;
while(beg<end){
if(s.charAt(beg)!=s.charAt(end)){
return false;
}
beg++;
end--;
}
return true;
}
public int MinInsert(String s){
int min=0;
if(isPaindrome(s)){
return min;
}
min++;
while(true){
ArrayList<String> temp=comboes(s,min);
if(hasPalindrome(temp)){
return min;
}
else
min++;
}
}
/*
* Returns an arraylist of strings, in which n characters are removed
*
*/
public ArrayList<String> comboes(String s,int n){
ArrayList<String> results=new ArrayList<String>();
if(n==1){
for(int i=0;i<s.length();i++){
String text="";
for(int j=0;j<s.length();j++){
if(i!=j){
text=text+""+s.charAt(j);
}
}
results.add(text);
}
}
else{
ArrayList<String> temp=new ArrayList<String>();
for(int i=0;i<s.length();i++){
String tempString="";
for(int j=0;j<s.length();j++){
if(i!=j){
tempString=tempString+s.charAt(j);
}
}
temp=comboes(tempString, n-1);
for(int j=0;j<temp.size();j++){
results.add(""+temp.get(j));
}
}
}
return results;
}
public boolean hasPalindrome(ArrayList<String> text){
for(String temp:text){
if(isPaindrome(temp)){
return true;
}
}
return false;
}
public static void main(String[] args)throws IOException
{
System.out.println("Enter the word :");
MinPalin obj=new MinPalin();
BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
int n=obj.MinInsert(r.readLine());
System.out.println("Characters needed : "+n);
}
}
希望这能帮到您。
- Yuvaraj K C
1
Python解决方案：
import math
def isPalindrome(s):
return s[:len(s)/2] == s[int(math.ceil(len(s)/2.0)):][::-1]
def numPalindrome(s):
for i in range(len(s)):
if isPalindrome(s[:len(s) - i]) or isPalindrome(s[i:]):
return i
- tiagob
1
简单地
static int GetNumForPalindrome(string str)
{
int count = 0;
for (int start = 0, end = str.Length - 1; start < end; ++start)
{
if (str[start] != str[end])
++count;
else --end;
}
return count;
}
static void Main(string[] args)
{
while (true)
{
Console.WriteLine(GetNumForPalindrome(Console.ReadLine()).ToString());
}
}
- Ahmed
1
输入“baob”怎么办？我需要3个字符来构成回文。您的程序将执行以下操作：
str[0] == 'b' == str[3]' -> start == 1, end == 2-> str[1] == 'a', str[2] == 'o'->count == 1, start == 2, end == 2` -> 返回1。 - Krab1
我认为一个更简单的解决方案是在字符串中逐个字符地查找子回文的开头。
void makePalindrome(const char* str)
{
int len = strlen(str);
int fp=0, bp=len-1, begin=0, end=bp;
// fp and bp are used to look for matches.
// begin and end represent the begin and end of a possible sub palindrome
while(fp < bp)
{
if(str[fp] == str[bp])
{
fp++; //move back and front pointers.
bp--;
}
else{
if(bp == end) //If no match found yet, just move forward.
{
fp++;
begin++;
}
else
{
begin++; //Since begin isn't feasible, move begin forward
fp = begin; //Reset fp and bp to their respective positions.
bp = end;
}
}
}
int minLenPal = len + begin; //Minimum Length of Palindrome
char a[minLenPal+1];
{ //Build the Palindrome a
strcpy(a,str);
for(int i = 0; i< begin; i++)
a[minLenPal-i-1] = str[i];
a[minLenPal] ='\0';
}
cout<<"For String "<<str<<", minimum characters to be added is "
<<begin<<". Palindrome is "<<a<<endl;
}
这是我的第一篇帖子，请编辑掉任何格式错误。
- Kishu
1
这就像是找到两个字符串之间的编辑距离，这是一个标准的动态规划问题。你知道字符串的长度，所以将字符串分成两半。你需要找到最少的字符数来将一个字符串转换为另一个字符串。现在有改进过的编辑距离算法可用。
使用这个算法，你可以在O(n^2)的时间复杂度内解决这个问题。
使用这个算法，你可以在O(n^2)的时间复杂度内解决这个问题。
- unj2
1
除了Pax的回答之外，您还可以使用“字符串算法宝石”中描述的线性时间Manacher算法来计算文本中回文半径。使用这个算法，您可以轻松地在线性时间内计算文本末尾最长回文的长度。我认为这加速了Pax的算法到线性时间。
编辑：
Pax的算法基于一个假设，即您只能在字符串的末尾添加字符。如果您尝试使用BAAABAAB进行测试，您将得到BAAABAABAAAB，但是您可以通过插入一个字符将其变成BAABABAAB，或者如果您只能在末尾或开头添加，则可以将其变成BAABAAABAAB。
编辑：
Pax的算法基于一个假设，即您只能在字符串的末尾添加字符。如果您尝试使用BAAABAAB进行测试，您将得到BAAABAABAAAB，但是您可以通过插入一个字符将其变成BAABABAAB，或者如果您只能在末尾或开头添加，则可以将其变成BAABAAABAAB。
- niteria
0
#include <iostream>
#include<string.h>
using namespace std;
int f(char t[],int i,int j)
{
int c1=0,c2=0,c3=0;
int r;
if(i<j)
{
if(t[i]==t[j])
{
c3=f(t,i+1,j-1);
cout<<"3 "<<c3<<"\n";
return c3;
}
else
{
c1=f(t,i+1,j);
cout<<"c1 "<<c1<<"\n";
c2=f(t,i,j-1);
cout<<"c2 "<<c2<<"\n";
if(c1<c2)
{
c1++;
cout<<"1 "<<c1<<"\n";
return c1;
}
if(c2<c1)
{
c2++;
cout<<"2 "<<c2<<"\n";
return c2;
}
if(c1==c2)
{
c1++;
c2++;
cout<<"4 "<<c1<<"\n";
return c1;
}
}
}
if(i>=j)
{
cout<<"5 "<<c1<<"\n";
return c1;
}
}
int main()
{
int i,j,c=0,n=0;
char s[10];
cout<<"enter the string";
cin>>s;
for(i=0;s[i]!='\0';i++)
n++;
i=0;
j=n-1;
c=f(s,i,j);
cout<<c;
return 0;
}
- satiksha
0
这是我的两分钱。可能不是最快的，但如果你喜欢Lambda表达式，它很简洁易懂。
static void Main(string[] args)
{
string pal = "ABB";
Console.WriteLine(minPallyChars(pal).ToString());
}
static int minPallyChars(string pal)
{
return Enumerable.Range(0, pal.Length).First(x => IsPally(pal + ReverseStr(pal.Substring(0, x))));
}
static bool IsPally(string value)
{
return value == ReverseStr(value);
}
public static string ReverseStr(string value)
{
return new string(value.Reverse().ToArray());
}
- deepee1
0
创建一个函数，接受一个字符串和一个数字n，然后通过添加n个额外的字符来尝试将字符串转换成回文字符串。
对于n=0..不做任何操作
对于n=1..附加第一个字符..以此类推
从n=0到初始字符串的长度运行此函数..
返回成功的第一个n值即为答案。
对于n=0..不做任何操作
对于n=1..附加第一个字符..以此类推
从n=0到初始字符串的长度运行此函数..
返回成功的第一个n值即为答案。
- Aditya Mukherji
1
这个方法可以运行，但是渐进复杂度比Pax算法更差。 - Brian
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接