Ich wurde diese Frage in einem Telefoninterview für ein Sommerpraktikum gestellt und versuchte, eine n * m-Komplexitätslösung (obwohl sie nicht genau war) in Java zu finden.
Ich habe eine Funktion, die 2 Zeichenfolgen akzeptiert, angenommen "common" und "cmn". Es sollte True zurückgeben, basierend auf der Tatsache, dass "c", "m", "n" in der gleichen Reihenfolge in "common" vorkommen. Wenn die Argumente jedoch "common" und "omn" wären, würde sie False zurückgeben, obwohl sie in der gleichen Reihenfolge auftreten, aber 'm' auch nach 'o' erscheint (was die Musterübereinstimmungsbedingung nicht erfüllt)
Ich habe mit Hashmaps und Ascii Arrays darüber gearbeitet, aber noch keine überzeugende Lösung gefunden! Von dem, was ich bis jetzt gelesen habe, kann es mit Boyer-Moore- oder Levenshtein-Distanzalgorithmen verwandt werden?
Hoffe auf Atempause bei stackoverflow! :)
Bearbeiten : In einigen Antworten wird die Wortlänge reduziert oder ein Hashset erstellt. Aber nach meinem Verständnis kann diese Frage nicht mit Hash-Sets gemacht werden, weil das Auftreten / Wiederholen jedes Zeichens in der ersten Zeichenkette seine eigene Bedeutung hat. PASS-Bedingungen - "con", "cmn", "cm", "cn", "mn", "auf", "co". FAIL-Bedingungen, die anders aussehen könnten - "com", "omn", "mon", "om". Diese sind FALSE / FAIL, weil "o" sowohl vor als auch nach "m" auftritt. Ein anderes Beispiel - "google", "ole" würde PASS, aber "google", "gol" würde fehlschlagen, weil "o" auch vor "g" erscheint!
Ich denke, es ist ziemlich einfach. Führen Sie das Muster durch, und für jedes Zeichen wird der Index des letzten Vorkommens in der Zeichenfolge abgerufen. Der Index muss immer größer werden, andernfalls wird false zurückgegeben. Also im Pseudocode:
%Vor% Bearbeiten: Sie könnten den Code weiter verbessern, indem Sie index als Startindex an die Methode lastIndexOf übergeben. Dann müssten Sie checkindex nicht mit index vergleichen und der Algorithmus wäre schneller.
Aktualisiert: Ein Fehler im Algorithmus wurde behoben. Zusätzliche Bedingung hinzugefügt, um die Reihenfolge der Buchstaben im Muster zu berücksichtigen.
Eine ausgezeichnete Frage und ein paar Stunden Recherche und ich denke, ich habe die Lösung gefunden. Lassen Sie mich zuerst versuchen, die Frage in einem anderen Ansatz zu erklären.
Voraussetzung:
Betrachten wir dasselbe Beispiel 'common' (mainString) und 'cmn' (subString). Zunächst müssen wir uns darüber im Klaren sein, dass sich alle Zeichen innerhalb des mainString und auch des subString wiederholen können und da das Muster, auf das wir uns konzentrieren, eine große Rolle spielt. Also müssen wir wissen:
Lasst uns das in der Warteschleife halten und weitermachen und die Muster noch ein wenig überprüfen. Für das Wort common müssen wir herausfinden, ob das bestimmte Muster cmn vorhanden ist oder nicht. Die verschiedenen möglichen Muster sind: - (Vorrang gilt)
Zu jedem Zeitpunkt muss dieser Vorrang und Vergleich gültig sein. Da der Vorrang eine große Rolle spielt, müssen wir den Index jedes einzelnen Zeichens haben, anstatt die verschiedenen Muster zu speichern.
Lösung
Der erste Teil der Lösung besteht darin, eine Hash-Tabelle mit den folgenden Kriterien zu erstellen: -
Zweiter und Hauptteil des Mustervergleichs: -
Überprüfen Sie vor dem Schleifeninkrement zwei Bedingungen
%Vor%Zeigen Sie die Flagge an
NB: Da ich in Java nicht so vielseitig bin, habe ich den Code nicht eingereicht. Aber jemand kann versuchen, meine Idee zu implementieren
Ich habe diese Frage in ineffizienter Weise selbst gemacht, aber es gibt ein genaues Ergebnis! Ich würde mich freuen, wenn jemand daraus einen effizienten Code / Algorithmus ausmachen kann!
Erstellen Sie eine Funktion "Check", die 2 Strings als Argumente akzeptiert. Überprüfen Sie jedes Zeichen von String 2 in String 1. Die Reihenfolge des Auftretens jedes Zeichens von s2 sollte in S1 als wahr bestätigt werden.
Wie man beobachten kann, ist dies eine Bruteforce-Methode ... Ich denke, O (N ^ 3)
%Vor%Ist es in O (n log n) nicht möglich?
Schritt 1: Verringern Sie die Zeichenfolge, indem Sie alle rechts angezeigten Zeichen entfernen. Genau genommen müssen Sie nur Zeichen löschen, wenn sie in der Zeichenkette erscheinen, die Sie überprüfen.
%Vor%Schritt 2, überprüfen Sie die Eindämmung.
%Vor%Und um Ihre zweite Frage zu beantworten, nein, Levenshtein Abstand wird Ihnen nicht helfen, da es die Eigenschaft hat, dass, wenn Sie die Argumente austauschen, die Ausgabe die gleiche ist, aber der Algo nicht will.
Ich würde dies als einen der schlimmsten Codeabschnitte, die ich je geschrieben habe, oder als eines der schlechtesten Codebeispiele im Stackoverflow betrachten ... aber rate mal ... alle deine Bedingungen sind erfüllt!
Kein Algorithmus konnte wirklich zu dem Bedarf passen, also habe ich nur Bruteforce benutzt ... probiere es aus ...
Und ich könnte mich nur weniger für die Komplexität von Raum und Zeit interessieren ... mein Ziel war es zuerst zu versuchen und es zu lösen ... und es vielleicht später zu verbessern!
-IvarD
Ich denke, dies ist kein Test Ihrer Informatikgrundlagen, sondern mehr, was Sie praktisch in der Java-Programmierumgebung tun würden.
Sie könnten einen regulären Ausdruck aus dem zweiten Argument konstruieren, d. h.
%Vor%... und testen Sie dann die Kandidaten-Zeichenfolge, indem Sie entweder String.matches (...) oder mit Muster Klasse.
In generischer Form sollte die Konstruktion der RegExp in den folgenden Zeilen sein.
exp - & gt; in [0] . * + für jedes x: 2 - & gt; in.Länge {( in [x-1] + [^ in [x-2]] * + in [x] )}
zum Beispiel:
demmn - & gt; d. * e [^ d] * m [^ e] * m [^ m] * n
Ich habe es selbst auf eine andere Art und Weise versucht. Teilen Sie einfach meine Lösung.
Öffentliche Klasse PatternMatch {
%Vor%}