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

Question

По заданной строке определите, сколько минимум символов необходимо, чтобы слово стало палиндромом. Примеры:

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

Answer 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.

Преобразование этого метода в «код»:

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

Answer 2

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

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

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

Представьте, что строка 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);
    }
}

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

Answer 3

Я думаю, что более простым решением было бы найти начало подпалиндрома в строке, перемещая символ за символом.

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

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

Answer 4

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

Answer 5

В дополнение к ответу Пакс. Вы можете использовать алгоритм Манахера с линейным временем, описанный в «Драгоценностях струнологии», чтобы вычислить радиусы палиндромов в тексте. Используя это, вы можете легко вычислить длину самого длинного палиндрома в конце текста за линейное время. Я думаю, что это ускоряет алгоритм Пакса к линейному времени.

EDIT:

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

Answer 6

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

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

Answer 7

просто

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

        }

    }

Answer 8

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

Answer 9

Вот мои 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());
    }

Answer 10

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