Как определить наименьшее количество символов для создания палиндрома?

Ответ 1

Только алгоритмы, так как это, вероятно, домашнее задание [Извинения перед Раймондом, это вопрос интервью, а не домашнее задание, поскольку его изменения/комментарии разъясняются. Тем не менее, алгоритмы и добавленный псевдокод все еще действительны для этой цели, и я добавил код C в конце].

Вам нужно найти самый длинный палиндром в конце строки. Алгоритм, чтобы увидеть, является ли строка палиндром, можно создать, просто выполнив один указатель с начала строки и один с конца, проверяя, что символы, на которые они ссылаются, идентичны, пока они не встречаются посередине. Что-то вроде:

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.

Преобразование этого метода в "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 + "."

Для тех, кто меньше интересуется псевдокодом, здесь тестовая программа в 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
========================================

Ответ 2

Я видел этот вопрос на конкурсе один раз. Тогда я был в тупике.

Но я думаю, что получил это после обсуждения с моими друзьями. Дело в том, чтобы найти минимальные символы для вставки в строку, вам нужно найти самый длинный палиндром с центром.

Возьмите строку "accaz"

Представьте, что строка accaz - это палиндром acca с z, вставленным в конец. Поэтому нам нужно добавить другое значение z в начале. Другая строка: "mykma"

Представьте, что это mym с двумя символами k и вставленными в него. Поэтому нам нужно еще два символа, чтобы сделать его палиндром. (палиндром будет аткикмой).

Я написал программу на 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);
    }
}

Надеюсь, что это поможет.

Ответ 3

просто

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

Это похоже на поиск расстояния редактирования между двумя строками, что является стандартной проблемой динамического программирования. Вы знаете длину строки, поэтому разделите строку на половину. Вам нужно найти меньшее количество символов для добавления, чтобы преобразовать одну строку в другую. Изменено Редактировать алгоритмы дистанции.

Используя этот алгоритм, вы можете решить проблему в O (n ^ 2).

Ответ 5

В дополнение к ответу Pax. Вы можете использовать алгоритм линейного времени Manacher, описанный в "Jewels of stringology", для вычисления радиусов палиндромов в тексте. Используя это, вы можете легко вычислить длину самого длинного палиндрома в конце текста в линейном времени. Я думаю, что это ускоряет алгоритм Pax до линейного времени.

EDIT:

Алгоритм Pax работает в предположении, что вы можете добавлять символы только в конце строки. Попробуйте с BAAABAAB, вы получите BAAABAABAAAB, но можете включить его в BAABABAAB с одной вставкой или BAABAAABAAB, если вы можете добавить только в конце или в начале.

Ответ 6

Решение 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

Ответ 7

Я думаю, что более простым решением было бы найти начало вспомогательного палиндрома в строке, перемещая 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;
}

Это мое первое сообщение, поэтому, пожалуйста, отредактируйте любые ошибки форматирования.

Ответ 8

сделать функцию, которая принимает строку и число n, а затем пытается сделать строку в палиндром, добавив n дополнительных символов.
для n = 0.. ничего не делать
для n = 1.. добавьте первый char.. и так далее запустите эту функцию от n = 0 до длины строки intial.
первое число n, для которого оно возвращает успех.. thats your answer

Ответ 9

Вот мои 2 цента. Не может быть самым быстрым, но это будет кратким и простым, если вы попадете в Лямбдас.

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