Dies ist eine Interviewfrage, die auf Zeit optimiert werden muss.
Angenommen, Sie haben ein 2-dimensionales Array und Sie haben eine Zeichenkette "Amazon" im Array, so dass die einzelnen Zeichen von links nach rechts, von rechts nach links, von oben nach unten und von unten nach oben angezeigt werden können.
Ich werde es mit einem Beispiel erklären:
%Vor%Das obige Array hat zwei Amazon-Strings. Sie müssen die Anzahl der Anzahl solcher Zeichenfolgen zurückgeben.
Ich habe ein einfaches bfs gemacht, jedes Mal, wenn das erste Zeichen der Zeichenfolge toFind (in Ihrem Fall AMAZON) mit einem Zeichen im 2D-Array übereinstimmt. Ein einfaches besuchtes 2D-Array wird verwendet, um in einer Iteration nach markierten Zeichen zu suchen:
%Vor%Sie können ein BFS von jeder Zelle der Matrix mit "A" ausführen und die Anzahl der Möglichkeiten zählen, wie Amazon gebaut werden kann. Schließlich füge sie alle hinzu.
Kanten: Ein benachbarter (oben, unten, links, rechts) Knoten (Zelle) hat eine gerichtete Kante vom aktuellen Knoten (Zelle), wenn er das nächste Zeichen von Amazon enthält. Beispielsweise haben alle benachbarten Knoten mit 'N' eine gerichtete Kante von dem Knoten mit 'O'.
Sie haben nur ein Beispiel gegeben. Wenn:
Dann müssen Sie nur zählen, wie viele dieser sich nicht wiederholenden Buchstaben es gibt. Zum Beispiel müssen Sie mit 'AMAZON' nur zählen, wie viele 'Z' (oder 'M', oder 'O' oder 'N') im Array sind.
Das ist nicht so allgemein wie ein Pfadfindungsalgorithmus, aber definitiv schneller.
Beginnen Sie mit der Matrix [i, j] und versuchen Sie, "Amazon" in allen vier Richtungen zu verfolgen
a. Sie können BFS oder DFS verwenden
b. Wenn gefunden, erhöhen Sie die Anzahl um 1
c. Falls nicht gefunden, fahre fort mit
Zeitkomplexität = O (N ^ 2 + N) {mit DFS}
Erstellen Sie eine dreidimensionale Tabelle, wobei sich jede Position in der Matrix auf ein Array bezieht, das jeden Buchstaben im Alphabet darstellt. Führen Sie zwei Iterationen gleichzeitig von oben, von links nach rechts und von rechts nach links, zeilenweise durch: Wenn die Zeichenfolge existiert, werden Sie entweder ihren ersten oder letzten Buchstaben finden (die einzige Möglichkeit, einen mittleren Buchstaben zu finden, ist, wenn Sie bereits haben) den ersten oder letzten Teil des verbundenen Spiels gesehen). Aggregieren Sie Ihre Links-Rechts-Ergebnisse, aber legen Sie die Position des Elements darunter am Index fest, der das nächste mögliche Zeichen mit der aktuellen Länge und Richtung darstellt. Wenn eine Tabellenübereinstimmung gefunden wird, wandeln Sie sie in eine vollständige oder eine andere teilweise Übereinstimmung um (jede solche Zelle mit Buchstaben + Position kann mehr als eine mögliche Übereinstimmung enthalten).
Ich habe einen Java-Code geschrieben, der diese Frage löst
Aber es ist eine teure Lösung in Bezug auf die zeitliche Komplexität
Wenn ich das 2D-Array durchquere und nach 'A' suche, dann durchquere ich dieses Element in vier Richtungen, suche nach M und dann nach A und so weiter
Das Worst-Case-Szenario, wenn wir 1 Scan des Arrays annehmen, ist also n ^ 2 und die Länge des Wortes, das wir scannen, ist K
wird
seinO (N ^ 2 * K ^ 4) die 4 hier ist für die 4 Richtungen, die wir suchen müssen
Hier ist die vollständig laufende Klasse
%Vor%}
Tags und Links algorithm time-complexity