¿Cómo puedo calcular el número de caracteres necesarios para convertir una cadena en un palíndromo?

Question

Hace poco encontré un problema concurso que le pide que calcule el número mínimo de caracteres que debe ser insertado (en cualquier lugar) en una cadena para convertirlo en un palíndromo.

Por ejemplo, dada la cadena: "ABCBD" podemos convertirlo en un palíndromo mediante la inserción de sólo dos personajes: uno después de "a" y otro después de "d": " d bcbd < b> a ".

Esto parece ser una generalización de un problema similar que pide la misma cosa, excepto caracteres sólo se pueden añadir al final -. Esto tiene una solución bastante simple en O (N) utilizando tablas hash

He estado tratando de modificar el algoritmo de distancia Levenshtein para resolver este problema, pero Haven' t sido exitosa. Cualquier ayuda sobre cómo resolver esto (que no necesariamente tiene que ser eficiente, sólo estoy interesado en cualquier solución DP) sería apreciada.

Answer 1

Nota: Esto es sólo una curiosidad. Dav propuso un algoritmo que puede ser modificado para algoritmo de DP para funcionar en O (n ^ 2) tiempo y O (n ^ 2) de espacio fácilmente (y tal vez O (n) con una mejor contabilidad).

Por supuesto, este algoritmo 'ingenua' en realidad podría ser útil si usted decide cambiar las operaciones permitidas.

---

Aquí es un 'algoritmo de naive'ish, lo que probablemente se puede hacer más rápido con la contabilidad inteligente.

Dada una cadena, que supongo que la mitad del palíndromo resultante y luego tratar de calcular el número de inserciones requeridas para hacer la cadena de un palíndromo en torno a esa media.

Si la cadena es de longitud n, hay 2n + 1 posibles middles (Cada personaje, entre dos personajes, justo antes y justo después de la cadena).

Supongamos que consideramos un medio que nos da dos cadenas L y R (uno a la izquierda y otro a la derecha).

Si estamos usando insertos, creo que el algoritmo común más larga subsecuencia (que es un DP algoritmo) se puede usar ahora el crear una cadena 'super' que contiene tanto L y reverso de R, ver más corta común supersequence .

Escoja el medio que le da los insertos número más pequeño.

Este es O (n ^ 3) Creo. (Nota: No he intentado demostrar que es verdad).

Answer 2

Mi C # solución busca caracteres repetidos en una cadena y los utiliza para reducir el número de inserciones. En una palabra como programa , que utilizan los caracteres 'r' como límite. En el interior de la 'r, hago que un palíndromo (de forma recursiva). Fuera de la 'r, que reflejan las personajes de la izquierda y de la derecha.

Algunas entradas tienen más de una salida más corta: salida puede ser toutptuot o outuputuo . Mi solución sólo selecciona una de las posibilidades.

Algunas ejemplo ejecuta:

• radar -> radar , 0 inserciones
• esystem -> metsystem , 2 inserciones
• mensaje -> megassagem , 3 inserciones
• StackExchange -> stegnahckexekchangets , 8 inserciones

En primer lugar tengo que comprobar si hay una entrada que ya es un 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;
}

A continuación, tengo que encontrar alguna caracteres repetidos en la entrada. Puede haber más de uno. La palabra mensaje tiene dos personajes más repetidos ( 'e' y '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;
}

Mi algoritmo es aquí:

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

Tenga en cuenta que se necesita una función 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 # solución recursiva añadiendo al final de la cadena:

Hay 2 casos base. Cuando la longitud es 1 o 2. caso recursiva: Si los extremos son iguales, entonces palíndromo que la cadena interior sin los extremos y volver que con los extremos. Si los extremos no son iguales, a continuación, añadir el primer carácter hasta el final y hacer que el palíndromo cadena interna que incluye el último carácter anterior. devolver eso.

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