Come posso calcolare il numero di caratteri necessari per trasformare una stringa in un palindromo?

Question

Recentemente ho trovato un problema di concorso che ti chiede di calcolare il numero minimo di caratteri che devono essere inseriti (ovunque) in una stringa per trasformarla in un palindromo.

Ad esempio, data la stringa:"abcbd" possiamo trasformarlo in palindromo inserendo solo due caratteri:uno dopo "a" e un altro dopo "d":"UNDbcbdUN".

Questa sembra essere una generalizzazione di un problema simile che richiede la stessa cosa, tranne per il fatto che i caratteri possono essere aggiunti solo alla fine: ha una soluzione piuttosto semplice in O(N) utilizzando le tabelle hash.

Ho provato a modificare il Algoritmo della distanza di Levenshtein per risolvere questo problema, ma non hanno avuto successo.Qualsiasi aiuto su come risolvere questo problema (non deve necessariamente essere efficiente, sono solo interessato a qualsiasi soluzione DP) sarebbe apprezzato.

Answer 1

Nota: Questa è solo una curiosità. Dav proposto un algoritmo che può essere modificato per algoritmo DP per l'esecuzione in O (n ^ 2) tempo e O (n ^ 2) spazio facilmente (e forse O (n) con una migliore contabilità).

Naturalmente, questo algoritmo 'ingenuo' potrebbe in realtà rivelarsi utile se si decide di modificare le operazioni consentite.

---

Ecco un 'algoritmo di naive'ish, che probabilmente può essere fatto più velocemente con la contabilità intelligente.

Data una stringa, indoviniamo la metà del palindromo risultante e quindi provare a calcolare il numero di inserti necessari per rendere la stringa palindroma intorno a quella centrale.

Se la stringa è di lunghezza n, vi sono 2n + 1 possibilità mediane (Ogni carattere, tra due caratteri, appena prima e appena dopo la stringa).

Supponiamo consideriamo un mezzo che ci dà due stringhe L e R (uno a sinistra e uno a destra).

Se stiamo usando inserti, credo che il Longest Common Subsequence algoritmo (che è un DP algoritmo) può ora essere utilizzato il creare una stringa 'super' che contiene sia L e inversa di R, vedi Shortest comune supersequence .

Pick mezzo che vi dà più piccoli inserti numero.

Questa è O (n ^ 3) Credo. (Nota: io non ho provato dimostrando che è vero).

Answer 2

La mia soluzione C# cerca caratteri ripetuti in una stringa e li utilizza per ridurre il numero di inserimenti.In una parola come programma, utilizzo i caratteri "r" come confine.All'interno delle "r", lo rendo palindromo (ricorsivamente).Al di fuori delle "r", rispecchio i caratteri a sinistra e a destra.

Alcuni input hanno più di un output più breve: produzione può essere tutto O outuputuo.La mia soluzione seleziona solo una delle possibilità.

Alcuni esempi vengono eseguiti:

• radar -> radar, 0 inserimenti
• esistema -> metsystem, 2 inserimenti
• Messaggio -> megassagem, 3 inserimenti
• stackexchange -> stegnahckexekchangets, 8 inserimenti

Per prima cosa devo verificare se un input è già palindromo:

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

Quindi devo trovare eventuali caratteri ripetuti nell'input.Potrebbero essercene più di uno.La parola Messaggio ha due caratteri più ripetuti ("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;
}

Il mio algoritmo è qui:

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

Tieni presente che hai bisogno di una funzione Reverse:

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 # soluzione ricorsiva aggiungendo alla fine della stringa:

Ci sono 2 casi di base. Quando la lunghezza è 1 o 2. caso ricorsivo: se gli estremi sono uguali, allora rendere palindromo la stringa interna senza gli estremi e restituire che con gli estremi. Se gli estremi non sono uguali, quindi aggiungere il primo carattere fino alla fine e fare il palindromo stringa interno compreso l'ultimo carattere precedente. restituire questo.

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