如何确定创建回文的最少字符数？

Given a string, figure out how many characters minimum are needed to make the word a palindrome. Examples:

给定一个字符串,找出使该单词成为回文所需的最小字符数。例子:

ABBA : 0 (already a palindrome)
ABB: 1
FAE: 2
FOO: 1

10 个解决方案

#1

Algorithms only, since this is probably homework [Apologies to Raymond, it's an interview question rather than homework, as his edits/comments make clear. However, the algorithms and added pseudo-code are still valid for that purpose, and I've added some C code at the end].

算法,因为这可能是家庭作业[道歉雷蒙德,这是一个面试问题,而不是作业,因为他的编辑/评论清楚。但是,算法和添加的伪代码仍然有效,并且我最后添加了一些C代码。

You need to find the longest palindrome at the end of the string. An algorithm to see if a string is a palindrome can be created by simply running one pointer from the start of the string and one from the end, checking that the characters they refer to are identical, until they meet in the middle. Something like:

你需要在弦的末尾找到最长的回文。可以通过简单地从字符串的开头运行一个指针和从末尾运行一个指针来创建查看字符串是回文结构的算法,检查它们引用的字符是否相同,直到它们在中间相遇。就像是:

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

Try that with the full string. If that doesn't work, save the first character on a stack then see if the remaining characters form a palindrome. If that doesn't work, save the second character as well and check again from the third character onwards.

尝试使用完整的字符串。如果这不起作用,请将第一个字符保存在堆栈中,然后查看剩余的字符是否形成回文。如果这不起作用,请同时保存第二个字符,然后再从第三个字符开始检查。

Eventually you'll end up with a series of saved characters and the remaining string which is a palindrome.

最终你会得到一系列保存的字符和剩下的字符串,这是一个回文。

Best case is if the original string was a palindrome in which case the stack will be empty. Worst case is one character left (a one-character string is automatically a palindrome) and all the others on the stack.

最好的情况是如果原始字符串是回文,在这种情况下堆栈将是空的。最坏的情况是剩下一个字符(一个字符的字符串自动为回文)和堆栈中的所有其他字符。

The number of characters you need to add to the end of the original string is the number of characters on the stack.

您需要添加到原始字符串末尾的字符数是堆栈中的字符数。

To actually make the palindrome, pop the characters off the stack one-by-one and put them at the start and the end of the palindromic string.

要实际制作回文,请逐个将字符从堆栈中弹出并将它们放在回文字符串的开头和结尾处。

Examples:

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.

Converting this method to "code":

将此方法转换为“代码”:

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 + "."

For those less interested in pseudo-code, here's a test program in C which does the trick.

对于那些对伪代码不太感兴趣的人,这里有一个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;
}

Running this with:

运行此:

mkpalin abb abba fae foo deoxyribo

gives the output:

给出输出:

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
========================================

#2

I saw this question in a competition once. I was stumped then.

我曾经在比赛中看过这个问题。那时我很难过。

But i think i've gotten this after discussing it with my friends. The thing is to find the minimum characters to insert into a string, you need to find the longest palindrome its centered around.

但我想在与朋友们讨论之后我已经得到了这个。问题是找到要插入字符串的最小字符,你需要找到它居中的最长的回文。

Take the string "accaz"

拿字符串“accaz”

Imagine the string accaz is the palindrome acca with z inserted at the end. So we need to add another z at the start. Another string :"mykma"

想象一下,字符串accaz是最后插入z的回文acca。所以我们需要在开始时添加另一个z。另一个字符串:“mykma”

Imagine this to be mym with two characters k and a inserted into it. So we need to two more characters to make it a palindrome. (the palindrome would be amkykma).

想象一下,这是两个字符k和插入其中的mym。所以我们还需要两个字符才能使它成为回文。 (回文将是amkykma)。

I've written a program in Java implementing this.

我用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);
    }
}

Hope this helps.

希望这可以帮助。

#3

simply

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());

        }

    }

#4

This is like finding the edit distance between two strings, which is a standard dynamic programming problem. You know the length of the string so split the string into half. You need to find the least number of characters to add to transform one string to another. Modified Edit Distance Algorithms are now available.

这就像找到两个字符串之间的编辑距离,这是一个标准的动态编程问题。你知道字符串的长度,所以将字符串分成两半。您需要找到要添加的最少字符数以将一个字符串转换为另一个字符串。现在可以使用修改的编辑距离算法。

Using this algorithm, you can solve the problem in O(n^2).

使用此算法,您可以在O(n ^ 2)中解决问题。

#5

In addition to Pax's response. You can use linear time Manacher's algorithm described in "Jewels of stringology" to compute radiuses of palindromes within text. Using that you can easily compute the length of the longest palindrome at the end of the text in linear time. I think this speeds up Pax's algorithm to linear time.

除了Pax的回应。您可以使用“字符串宝石”中描述的线性时间Manacher算法来计算文本中的回文半径。使用它,您可以在线性时间内轻松计算文本末尾最长回文的长度。我认为这可以将Pax的算法加速到线性时间。

EDIT:

Pax's algorithm works on assumption you can only add characters at the end of the string. Try it with BAAABAAB, you'll get BAAABAABAAAB, but you can turn it into BAABABAAB with one insertion or BAABAAABAAB if if you can only add at the end or the beginning.

Pax的算法假设你只能在字符串的末尾添加字符。尝试使用BAAABAAB,您将获得BAAABAABAAAB,但如果您只能在结尾或开头添加,则可以通过一次插入或BAABAAABAAB将其转换为BAABABAAB。

#6

python solution:

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

#7

I think an easier solution would be to find the beginning of the sub palindrome in the string, moving char by char.

我认为一个更简单的解决方案是在字符串中找到子回文的开头,通过char移动char。

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;
}

This is my first post so please edit out any formatting mistakes.

这是我的第一篇文章,所以请编辑出任何格式错误。

#8

make a function that accepts a string and a number n and then tries to make the string into a palindrome by adding n additional characters..
for n=0.. do nothing
for n=1.. append the first char .. and so on
run this function from n=0 to the length of the intial string..
the first number n for which it returns success.. thats your answer

创建一个接受字符串和数字n的函数,然后尝试通过添加n个附加字符使字符串成为回文..对于n = 0 ..对n = 1不做任何事情..附加第一个字符..等等运行此函数从n = 0到初始字符串的长度..它为其返回成功的第一个数字n ..这就是你的答案

#9

Here's my 2 cents. May not be the fastest, but it is terse and simple to follow if you're into Lambdas.

这是我的2美分。可能不是最快的,但是如果你进入Lambdas,它就会很简洁。

    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());
    }

#10

#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;
}