Como posso calcular o número de caracteres necessários para transformar uma string em um palíndromo?

Question

Eu encontrei recentemente um problema concurso que pede-lhe para calcular o número mínimo de caracteres que deve ser inserido (em qualquer lugar) em uma string para transformá-lo em um palíndromo.

Por exemplo, dada a string: "abcbd" podemos transformá-lo em um palíndromo, inserindo apenas dois personagens: um após "a" e outro depois de "d": "a d bcbd < b> a ".

Esta parece ser uma generalização de um problema semelhante que pede a mesma coisa, exceto caracteres só podem ser adicionados no final -. Isso tem uma solução bastante simples em O (N), utilizando tabelas de hash

Eu tenho tentado modificar a Levenshtein algoritmo distância para resolver este problema, mas haven' t sido bem sucedida. Qualquer ajuda sobre como resolver isso (não necessariamente tem que ser eficiente, só estou interessado em qualquer solução DP) seria apreciada.

Answer 1

Nota: Esta é apenas uma curiosidade. Dav proposto um algoritmo que pode ser modificado para algoritmo DP para ser executado em O (n ^ 2) tempo e O (n ^ 2) espaço facilmente (e talvez O (n) com uma melhor contabilidade).

É claro, esse algoritmo 'ingênuo' pode realmente vir a calhar se você decidir mudar as operações permitidas.

---

Aqui está um 'algoritmo naive'ish, que provavelmente pode ser feito mais rápido com a contabilidade inteligente.

Dado uma string, que acho meio do palíndromo resultante e, em seguida, tentar calcular o número de inserções necessário para fazer a seqüência de um palíndromo em torno desse meio.

Se a string é de comprimento n, existem 2n + 1 middles possíveis (cada personagem, entre dois personagens, um pouco antes e logo após a string).

Suponha que consideramos um meio que nos dá duas cadeias L e R (uma para a esquerda e um para a direita).

Se estamos usando inserções, eu acredito que o algoritmo Longest Subsequence Comum (que é um DP algoritmo) agora pode ser usado a criar uma seqüência de 'super' que contém ambos L e reverter de R, consulte comum Shortest Superseqüência .

Escolha o meio que lhe dá os menores inserções numéricas.

Este é O (n ^ 3) eu acredito. . (Nota: provar Eu não tentei que é verdade)

Answer 2

Meu C aparência # solução para caracteres repetidos em uma string e usa-los para reduzir o número de inserções. Em uma palavra como programa , eu uso os personagens 'R' como um limite. Dentro do 'r do que faço que um palíndromo (de forma recursiva). Fora do 'r, I espelhar os caracteres à esquerda e à direita.

Algumas entradas têm mais de uma saída menor: saída pode ser toutptuot ou outuputuo . Minha solução seleciona apenas uma das possibilidades.

Alguns exemplos de corridas:

• radar -> radar , 0 inserções
• esystem -> metsystem , 2 inserções
• Mensagem -> megassagem , 3 inserções
• Stackexchange -> stegnahckexekchangets , 8 inserções

Primeiro eu preciso verificar se uma entrada já é um palíndromo:

public static bool IsPalindrome(string str)
{
    for (int left = 0, right = str.Length - 1; left < right; left++, right--)
    {
        if (str[left] != str[right])
            return false;
    }
    return true;
}

Então eu preciso encontrar quaisquer caracteres utilizadas na entrada. Pode haver mais de um. A palavra Mensagem tem dois personagens mais repetidas ( 'E' e 's'):

private static bool TryFindMostRepeatedChar(string str, out List<char> chs)
{
    chs = new List<char>();
    int maxCount = 1;

    var dict = new Dictionary<char, int>();
    foreach (var item in str)
    {
        int temp;
        if (dict.TryGetValue(item, out temp))
        {
            dict[item] = temp + 1;
            maxCount = temp + 1;
        }
        else
            dict.Add(item, 1);
    }

    foreach (var item in dict)
    {
        if (item.Value == maxCount)
            chs.Add(item.Key);
    }

    return maxCount > 1;
}

O meu algoritmo é aqui:

public static string MakePalindrome(string str)
{
    List<char> repeatedList;
    if (string.IsNullOrWhiteSpace(str) || IsPalindrome(str))
    {
        return str;
    }
    //If an input has repeated characters,
    //  use them to reduce the number of insertions
    else if (TryFindMostRepeatedChar(str, out repeatedList))
    {
        string shortestResult = null;
        foreach (var ch in repeatedList) //"program" -> { 'r' }
        {
            //find boundaries
            int iLeft = str.IndexOf(ch); // "program" -> 1
            int iRight = str.LastIndexOf(ch); // "program" -> 4

            //make a palindrome of the inside chars
            string inside = str.Substring(iLeft + 1, iRight - iLeft - 1); // "program" -> "og"
            string insidePal = MakePalindrome(inside); // "og" -> "ogo"

            string right = str.Substring(iRight + 1); // "program" -> "am"
            string rightRev = Reverse(right); // "program" -> "ma"

            string left = str.Substring(0, iLeft); // "program" -> "p"
            string leftRev = Reverse(left); // "p" -> "p"

            //Shave off extra chars in rightRev and leftRev
            //  When input = "message", this loop converts "meegassageem" to "megassagem",
            //    ("ee" to "e"), as long as the extra 'e' is an inserted char
            while (left.Length > 0 && rightRev.Length > 0 && 
                left[left.Length - 1] == rightRev[0])
            {
                rightRev = rightRev.Substring(1);
                leftRev = leftRev.Substring(1);
            }

            //piece together the result
            string result = left + rightRev + ch + insidePal + ch + right + leftRev;

            //find the shortest result for inputs that have multiple repeated characters
            if (shortestResult == null || result.Length < shortestResult.Length)
                shortestResult = result;
        }

        return shortestResult;
    }
    else
    {
        //For inputs that have no repeated characters, 
        //  just mirror the characters using the last character as the pivot.
        for (int i = str.Length - 2; i >= 0; i--)
        {
            str += str[i];
        }
        return str;
    }
}

Note que você precisa de uma função inversa:

public static string Reverse(string str)
{
    string result = "";
    for (int i = str.Length - 1; i >= 0; i--)
    {
        result += str[i];
    }
    return result;
}

Answer 3

C # solução recursiva adicionando ao final da string:

Existem 2 casos base. Quando o comprimento é 1 ou 2. caso recursiva: Se os extremos são iguais, então fazer palindrome a coluna interna sem os extremos e retorno que com os extremos. Se os extremos não são iguais, em seguida, adicione o primeiro caractere até o fim e fazer palindrome o coluna interna, incluindo o último caractere anterior. devolver isso.

public static string ConvertToPalindrome(string str) // By only adding characters at the end
    {
        if (str.Length == 1) return str; // base case 1
        if (str.Length == 2 && str[0] == str[1]) return str; // base case 2
        else
        {
            if (str[0] == str[str.Length - 1]) // keep the extremes and call                
                return str[0] + ConvertToPalindrome(str.Substring(1, str.Length - 2)) + str[str.Length - 1];
            else //Add the first character at the end and call
                return str[0] + ConvertToPalindrome(str.Substring(1, str.Length - 1)) + str[0];
        }
    }