给定一个字符串,找出最少需要多少个字符,使得该单词成为回文。 例如:
ABBA:0(已经是回文) ABB:1 FAE:2 FOO:1
由于这可能是一份作业,所以只提供算法。您需要找到字符串末尾的最长回文子串。可以通过创建一个算法来判断一个字符串是否为回文,方法是从字符串的开头和结尾分别运行两个指针,并检查它们所引用的字符是否相同,直到它们在中间相遇。类似这样:
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
========================================
我曾在一次比赛中看到这个问题,当时我很困惑。
但是经过和朋友们的讨论,我认为找到需要插入字符串的最小字符数,需要找到以其为中心的最长回文串。
以字符串 "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);
}
}
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
简单地
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());
}
}
str[0] == 'b' == str[3]' ->
start == 1, end == 2->
str[1] == 'a', str[2] == 'o'->
count == 1, start == 2, end == 2` -> 返回1。 - Krab我认为一个更简单的解决方案是在字符串中逐个字符地查找子回文的开头。
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;
}
这是我的第一篇帖子,请编辑掉任何格式错误。
#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;
}
这是我的两分钱。可能不是最快的,但如果你喜欢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());
}