Schreiben Sie eine Funktion, die zwei Zeichenketten vergleicht und eine dritte Zeichenkette zurückgibt, die nur die Buchstaben enthält, die in beiden vorkommen

Question

Ich habe diese Hausaufgabe. Und habe sie auf folgende Weise gelöst. Ich brauche Ihre Kommentare, ob dies ein guter Ansatz ist oder ob ich eine andere Datenstruktur verwenden muss, um die Aufgabe besser zu lösen.

    public string ReturnCommon(string firstString, string scndString)
    {
        StringBuilder newStb = new StringBuilder();
        if (firstString != null && scndString != null)
        {
            foreach (char ichar in firstString)
            {
                if (!newStb.ToString().Contains(ichar) && scndString.Contains(ichar))
                    newStb.Append(ichar);
            }
        }
        return newStb.ToString();
    }

Answer 1

Als alternative Lösung können Sie die Zeichenketten als Aufzählungszeichen betrachten und mit Intersect() wie diese:

    public static string Common(string first, string second)
    {
        return new string((first.Intersect(second)).ToArray());
    }

Answer 2

Für einen ersten Ansatz ist das in Ordnung, aber Sie können einige Verbesserungen vornehmen, und es gibt einen kleinen Fehler.

• Wenn b enthält ein Zeichen in a die bereits in c wiederholen Sie es.
• Um Wiederholungen zu vermeiden, könnten Sie eine Set um die Zeichen zu speichern, da ein Set wird es keine Wiederholungen geben.
• Zusammenbau von Saiten mit += Verkettung ist in der Regel ineffizient; erwägen Sie die Verwendung einer StringBuilder oder eine analoge String-Assembly-Klasse.
• Die Namen Ihrer Variablen sind nicht sehr aussagekräftig.
• Wenn a ou b leer sind, müssen Sie überhaupt keine Arbeit leisten! Geben Sie einfach eine leere Zeichenkette zurück.

Sie können auch über anspruchsvollere Verbesserungen nachdenken, indem Sie sich vorstellen, wie Ihr Algorithmus skaliert, wenn Sie anfangen, große Zeichenketten zu verwenden. Ein Ansatz könnte zum Beispiel sein, dass Sie, wenn eine Zeichenkette viel länger ist als die andere, die längere sortieren und Duplikate entfernen können. Dann kann man sehr schnell eine binäre Suche nach den Zeichen der kürzeren Zeichenfolge durchführen.

Answer 3

Um den letzten Vorschlag von John Feminella zu verbessern: Schneller als eine binäre Suche (für jede ausreichend lange Zeichenkette) wäre eine Suche in einem Hashset; oder eine Suche in einem 256-Elemente-Array von Booleschen, wenn diese ASCII- oder UTF8-Zeichen statt UTF16-Zeichen sind.

• Ein leeres Hashset oder ein leeres Array von Booleschen Variablen instanziieren; diese Variable benennen found .
• Für jedes Zeichen in der ersten Zeichenkette fügen Sie das Zeichen entweder dem Hashset hinzu (achten Sie aber auf doppelte Zeichen in der ersten Zeichenkette), oder setzen Sie das entsprechende Element in der found Array auf true; dies dauert linear O(n) Zeit.
• Für jedes Zeichen in der zweiten Zeichenkette wird geprüft, ob das Zeichen im Hashset vorhanden ist vorhanden ist oder ob das entsprechende Element im Array "found" wahr ist: Wenn gefunden, dann füge das Zeichen zur Rückgabezeichenkette hinzu und entferne das Zeichen auch aus dem Hashset entfernen oder das boolesche Element im Array löschen, so dass es nicht mehr gefunden wird (um doppelte Zeichen in der zweiten Zeichenkette zu vermeiden); dies dauert linear O(n) Zeit.

Answer 4

Scheint in Ordnung zu sein. Sie könnten je nach verwendeter Sprache ein paar Optimierungen vornehmen:

• Sie können die Buchstaben von b in einer geordneten Struktur sammeln (um die Suche danach zu beschleunigen), und wenn sie sich nicht wiederholt... besser (eine Menge).
• Sie können eine Art von StrignBuilder verwenden (wenn es sich um Java oder .Net handelt), um nicht bei jeder Verkettung innerhalb der Schleife eine neue Zeichenkette zu erstellen

Wie auch immer, dies sind Optimierungen, die gut für große, große Zeichenfolgen sind... so, ich weiß nicht, ob ihre apropiate auf Ihre Verwendung, oder die beabsichtigte Hausaufgaben.

Answer 5

Hängt ab von wie lange sind die Eingabezeichenfolgen, Was ist der Buchstabe und wie Die Ausgabe sollte wie folgt aussehen (Duplikate) gibt es einige andere Ansätze.

Zum Beispiel:

Wenn Buchstaben sind nur [A-Z] Zeichen y jeder Buchstabe sollte erscheinen nur einmal im Ausgabestring können Sie separate Zeichenfolge erstellen (oder Zeichentabelle) 'ABC...XZ' (nennen wir es letters ) und führen for each überschleifen letters und prüfen beide Eingabestrings mit jedem Buchstaben aus letters .

Diese ergibt 26 Schleifenwiederholungen y nicht mehr では 52 Anrufe de Contains() Methode für jeden Eingabestring - unabhängig davon, wie lang die Eingabestrings sind.