Wie kann ich die Anzahl der Zeichen berechnen benötigt, um eine Zeichenfolge in ein Palindrom zu verwandeln?

Question

Vor kurzem fand ich einen Wettbewerb Problem, dass Sie die minimale Anzahl von Zeichen zu berechnen, fragt die (überall) in einem String eingefügt werden muss, es in ein Palindrom zu machen.

Um zum Beispiel der Zeichenfolge gegeben: „abcbd“ wir es in ein Palindrom drehen können nur zwei Zeichen durch Einfügen: eines nach dem „a“ und einem anderen nach „d“: „a d bcbd < b> a “.

Dies scheint eine Verallgemeinerung von einem ähnlichen Problem zu sein, das für die gleiche Sache fragt, außer Zeichen können nur am Ende hinzugefügt werden. - dies hat eine ziemlich einfache Lösung in O (N) Hash-Tabellen mit

Ich habe versucht, den Levenshtein-Distanz-Algorithmus zu modifizieren, um dieses Problem zu lösen, aber haven‘ t erfolgreich. Jede Hilfe, wie dies zu lösen (es muss nicht unbedingt effizient sein muss, bin ich interessiert nur in jedem DP-Lösung) wird gebeten.

Answer 1

Hinweis: Dies ist nur eine Kuriosität. Dav vorgeschlagen, einen Algorithmus, dem DP-Algorithmus modifiziert werden kann, in O (n ^ 2) Zeit und O (n ^ 2) Raum leicht (und vielleicht O (n) mit einem besseren Buchhaltung).

auszuführen

Natürlich ist dieser ‚naiv‘ Algorithmus könnte in praktisch tatsächlich kommen, wenn Sie die erlaubten Operationen entscheiden zu ändern.

---

Hier ist ein ‚naive'ish Algorithmus, der wahrscheinlich schneller mit cleverer Buchhaltung gemacht werden kann.

ein String gegeben, wir raten die Mitte des resultierenden Palindrom und dann versuchen, die Anzahl der Einsätze zu berechnen benötigt, um die Zeichenfolge ein Palindrom um diese Mitte zu machen.

Wenn die Zeichenfolge der Länge n ist, gibt es 2n + 1 möglich middles (Jedes Zeichen zwischen zwei Zeichen, kurz vor und kurz nach der Zeichenfolge).

Angenommen, wir einen Mittelweg betrachten, die uns zwei Saiten L und R (eine nach links und eine nach rechts) gibt.

Wenn wir Einsätze verwenden, glaube ich, die Längste gemeinsame Subsequence Algorithmus (das ein DP Algorithmus) kann nun die eine ‚super‘ Zeichenfolge erstellt werden, die sowohl L enthält und Rückwärts R, siehe Shortest gemeinsame Super .

Wählen Sie die Mitte, die Ihnen die kleinste Anzahl Einsätze gibt.

Dies ist O (n ^ 3), glaube ich. . (Anmerkung: Ich habe nicht versucht zu beweisen, dass es wahr ist)

Answer 2

Meine C # Lösung sieht für wiederholte Zeichen in einem String und verwendet sie die Anzahl der Einfügungen zu reduzieren. In einem Wort wie Programm , verwende ich die ‚r‘ Zeichen als Grenze. Innerhalb des ‚r, ich mache, dass ein Palindrom (rekursiv). Außerhalb des ‚R, I spiegeln die Zeichen auf der linken und der rechten Seite.

Einige Eingänge haben mehr als eine kürzeste Ausgabe: Ausgang kann sein toutptuot oder outuputuo . Meine Lösung wählt nur eine der Möglichkeiten.

Einige Beispiel läuft:

• Radar -> Radar , 0 Einfügungen
• eSystem -> metsystem , 2 Einfügungen
• Nachricht -> megassagem , 3 Einfügungen
• Stack -> stegnahckexekchangets , 8 Einfügungen

Zuerst habe ich Notwendigkeit zu überprüfen, ob eine Eingabe bereits ein Palindrom:

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

Dann brauche ich in der Eingabe keine wiederholten Zeichen zu finden. Es kann mehr als eins sein. Das Wort Nachricht hat zwei am meisten wiederholte Zeichen ( 'e' und '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;
}

Mein Algorithmus ist hier:

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

Beachten Sie, dass Sie eine Reverse-Funktion benötigen:

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 # rekursive Lösung für das Ende der Zeichenfolge hinzufügen:

Es gibt zwei Grund Fälle. Wenn Länge 1 oder 2 rekursive Fall: Wenn die Extreme gleich sind, dann machen Palindrom die innere Saite ohne die Extreme und Rendite, die mit den Extremen. Wenn die Extreme nicht gleich sind, dann fügen Sie das erste Zeichen bis zum Ende und machen Palindrom die innerer Strang unter Berücksichtigung der vorherigen letzten Zeichen. Rückkehr, dass.

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