algorithm - saber - ¿Cómo puedo calcular la cantidad de caracteres necesarios para convertir una cadena en un palíndromo?

palindromo recursivo en c

Question

Recientemente encontré un problema de concurso que le pide que calcule el número mínimo de caracteres que deben insertarse (en cualquier lugar) en una cadena para convertirlo en un palíndromo.

Por ejemplo, dada la cadena: "abcbd" podemos convertirla en un palíndromo insertando solo dos caracteres: uno después de "a" y otro después de "d": "a d bcbd a ".

Esto parece ser una generalización de un problema similar que pide lo mismo, excepto que los caracteres solo se pueden agregar al final; esto tiene una solución bastante simple en O (N) usando tablas hash.

He estado tratando de modificar el algoritmo de distancia Levenshtein para resolver este problema, pero no he tenido éxito. Cualquier ayuda sobre cómo resolver esto (no necesariamente tiene que ser eficiente, solo me interesa cualquier solución DP) sería apreciada.

Answer 1

Mi solución C # busca caracteres repetidos en una cadena y los utiliza para reducir el número de inserciones. En una palabra como programa , uso los caracteres ''r'' como límite. Dentro de las r, lo hago un palíndromo (recursivamente). Fuera de las ''r'', reflejo los caracteres de la izquierda y la derecha.

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

Algún ejemplo corre:

• radar -> radar , 0 inserciones
• esystem -> metsystem , 2 inserciones
• mensaje -> megassagem , 3 inserciones
• stackexchange -> stegnahckexekchchets , 8 inserciones

Primero necesito verificar si una entrada 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;
}

Entonces necesito encontrar cualquier carácter repetido en la entrada. Puede haber más de uno. La palabra mensaje tiene los dos caracteres 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 está 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 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 2

Solución recursiva de C # que agrega al final de la cadena:

Hay 2 casos base. Cuando la longitud es 1 o 2. Caso recursivo: si los extremos son iguales, entonces haga palíndromos la cuerda interna sin los extremos y devuélvala con los extremos. Si los extremos no son iguales, a continuación, agregue el primer carácter al final y haga palíndromo la cadena interna, incluido el último carácter anterior. devuelve 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];
        }
    }

Answer 3

Nota: Esto es sólo una curiosidad. Dav propuso un algoritmo que puede modificarse al algoritmo DP para ejecutarse en tiempo O (n ^ 2) y espacio O (n ^ 2) fácilmente (y quizás O (n) con una mejor contabilidad).

Por supuesto, este algoritmo "ingenuo" podría ser útil si decide cambiar las operaciones permitidas.

Aquí hay un algoritmo "ingenuo", que probablemente se puede hacer más rápido con una contabilidad inteligente.

Dada una cadena, adivinamos la mitad del palíndromo resultante y luego intentamos calcular el número de inserciones necesarias para hacer de la cadena un palíndromo alrededor de esa mitad.

Si la cadena es de longitud n, hay 2n + 1 posibles medios (cada carácter, entre dos caracteres, justo antes y justo después de la cadena).

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

Si estamos usando inserciones, creo que ahora se puede usar el algoritmo más largo de subsecuencias comunes (que es un algoritmo DP) para crear una cadena ''super'' que contiene tanto L como el reverso de R, consulte la supersecuencia más corta .

Elija el centro que le da el número más pequeño de inserciones.

Esto es O (n ^ 3) creo. (Nota: no he intentado demostrar que es cierto).