Ein Amateur hat am Google Tech Dev Guide gearbeitet, einem von Google bereitgestellten Lernmaterial. Da er jedoch ein Außenseiter ist, werden die Inhalte beim Lesen auf Englisch nicht eingegeben. Ich habe es ins Japanische übersetzt, weil es effizienter wäre, es zu lesen, nachdem ich alles ins Japanische übersetzt habe. Ich hoffe es hilft jemandem.
Diesmal habe ich an Folgendem gearbeitet:
■ Titel Former Coding Interview Question: Find longest word in dictionary that is a subsequence of a given string
■ Verknüpfen https://techdevguide.withgoogle.com/paths/foundational/find-longest-word-in-dictionary-that-subsequence-of-given-string/#code-challenge
・ Implementiert mit Python 3.6 ・ Ich habe ohne besonderen Aufwand etwas gemacht, das dem verknüpften Greedy-Algorithmus entspricht.
def find_longest_word_in_string(letter, words):
i = 0
ok = ""
l = len(letter) - 1
for w in words:
j = 0
while j < l:
if w[0] == letter[j]:
j += 1
w = w[1:]
else:
j +=1
if w == "":
if len(ok) < len(words[i]):
ok = words[i]
i += 1
return(ok)
S = "abppplee"
D = ["jam", "jamboleeee", "able", "ale", "apple", "bale", "kangaroo"]
result = find_longest_word_in_string(S, D)
print(result)
Japanische Übersetzung der folgenden Erklärung.
■ Erklärung Verschiedene Methoden können als Lösungsansatz betrachtet werden (Zum Beispiel gibt es mehrere anwendbare Algorithmen). Mit anderen Worten, Ihre Fähigkeit und Ihr Wissen zur Problemlösung werden getestet.
■ Erzwungene Lösung Generieren Sie alle möglichen Teilzeichenfolgen von 2 ^ n aus der Zeichenfolge S und prüfen Sie, ob sie mit den Wörtern im Wörterbuch D übereinstimmen. Als kleine Optimierung sollte die zu vergleichende Zeichenfolge durch eine Hash-Tabelle oder einen Präfixbaum dargestellt werden, um die Suche effizienter zu gestalten.
■ Überprüfen Sie jedes Wort im Wörterbuch mit der gierigen Methode Mit der gierigen Methode kann bestätigt werden, ob das Wort w im Wörterbuch D eine Teilzeichenfolge von S ist. Scannen Sie S von Anfang an nach w [0]. Wenn w [0] in S gefunden wird, fahren Sie mit dem Scannen von der Position fort, an der w [0] für w [1] gefunden wurde, bis das gesamte S gescannt wurde oder alle in w enthaltenen Zeichen gefunden wurden. weitermachen.
Nach dem Sortieren in absteigender Reihenfolge nach der Länge der in D enthaltenen Wörter kann das obige Verfahren ausgeführt werden, und das erste Wort, das eine Teilzeichenfolge von S wird, kann als Erkennungsergebnis verwendet werden. Die Ausführungszeit beträgt O (N * W) aus der Anzahl der im Wörterbuch enthaltenen Wörter W und der Anzahl der in S enthaltenen Zeichen N.
Wenn die Länge des in D enthaltenen Wortes in der Länge von S nahe bei N liegt, ist die Ausführungszeit O (N * W) zunehmend optimal (weil die Eingabe O (N * W) ist). Im schlimmsten Fall ist es jedoch alles andere als optimal, wenn die Zeichenfolge S lang und die in D enthaltenen Wörter sehr kurz sind.
Sei L die Gesamtlänge der Buchstaben aller im Wörterbuch enthaltenen Wörter. In diesem Fall ist der beste Fall der Berechnungszeit O (N + L) (unter Berücksichtigung des Falls, in dem das Wort kürzer als S ist). Die Ausführungszeit des obigen Algorithmus beträgt jedoch O (N * W), und sie kann O (N * L) sein, wenn die im Wörterbuch enthaltenen Wörter eine bestimmte kleine Länge haben.
■ Wie man Gier verbessert Um das Wort w im Wörterbuch zu überprüfen, muss das Minimum i bekannt sein, für das der in w enthaltene Buchstabe c S [i] == c größer als die Position j hat, an der der Buchstabe S zuvor entspricht. Bitte beachten Sie dies. Die gierige Methode ist offensichtlich langsam, weil sie dies ohne nachzudenken scannt.
Die Vorverarbeitung S kann solche Operationen viel schneller machen. Erstellen Sie eine Karte mit Zeichen-> Erstellen Sie eine nach Zeichen sortierte Liste. Zum Beispiel, wenn S == "abppplee":
a -> [0] b -> [1] p -> [2, 3, 4] l -> [5] e -> [6, 7]
Wenn Sie wissen möchten, dass "Das vorherige Zeichen war X, wo stimmt das nächste Zeichen Y überein?", Suchen Sie in der Karte nach Y und führen Sie dann eine Zweiteilung durch, um die kleinste Position von X in der Liste zu finden. Suchen Sie die Nummer oder stellen Sie fest, dass sie nicht vorhanden ist (in diesem Fall sind die Wörter im S nicht in der richtigen Reihenfolge).
Diese Methode erfordert eine Dichotomie für jedes in D enthaltene Zeichen. Da in diesem Fall nur O (N) für die Vorverarbeitung von S erforderlich ist, wird die Gesamtverarbeitungszeit daher zu O (N + logN) * 1 und nähert sich der bestmöglichen Verarbeitungszeit.
Weiterentwickelter Ansatz: Da es sich um ein klassisches "Nachfolgewert" -Problem handelt, gibt es möglicherweise spezielle Datenstrukturen, mit denen Suchvorgänge noch schneller durchgeführt werden können. Die Verwendung des vEB-Baums verbessert beispielsweise die Ausführungszeit auf O (N + L * loglogN).
■ Optimale Annäherung von O (N + L) an kleine Zeichenfolgen (ich bin mir hier nicht sicher) Wenn die Größe der Zeichenfolge nur a-z oder eine bestimmte kleine Zahl ist, kann dies durch die oben erwähnte Ausführungszeit von O (N + L) gelöst werden.
Die tatsächliche Ausführungszeit beträgt O (N * A + L), wobei A die Anzahl der Alphabete ist. Anstatt einen spärlichen Ausdruck * 2 zu erstellen (Sie könnten ihn dicht machen). ← Ich bin mir nicht sicher. Anstelle von p-> [2, 3, 4] können Sie p-> [2, 2, 3, 4, -1, -1, -1, -1, -1] wählen, und der i-te Index geht direkt zur Abfrage. Generieren Sie eine Antwort. Diese Methode erfordert ein O (N) Leerzeichen für jedes Zeichen (O (NA) insgesamt), und die Vorverarbeitung benötigt Zeit. Daher ist es nicht für große Zeichenketten geeignet.
■ Der beste Weg für jede Zeichenfolge Verarbeiten Sie alle Wörter gleichzeitig, anstatt Wort für Wort zu verarbeiten.
Erstellen Sie zunächst einen Taple mit w und 0 für jedes in D enthaltene Wort w (z. B. (w, 0)). Diese Nummer ist der Buchstabe in w, der in S gefunden wurde, daher wurde zuerst keiner gefunden. Über taple t Lassen Sie das Wort tapple t.w und die in tapple enthaltene Zahl t.i sein (weil es ein Index ist).
Gruppieren Sie Wörter nach t.w [t.i](der Anfangswert von t.i ist 0, der Anfangswert ist also das erste Zeichen). Zum Beispiel ist im Beispiel D = {"fähig", "Ale", "Apfel", "Ballen", "Känguru"}, also
a -> [("able", 0), ("ale", 0), ("apple", 0)] b -> [("bale", 0)] k -> [("kangaroo", 0)]
Was wir hier tun, zeigt, nach welchen Wörtern als nächstes für die Buchstaben gesucht werden muss, die im S. zu finden sind.
Scannen Sie Zeichen für Zeichen nach S. Wenn das gescannte Zeichen c ist, wird t.i für jedes in Karte [c] enthaltene Taple um 1 erhöht und in Karte [t.w [t.i]] * 3 verschoben. Wenn t.i == t.w.length, verschieben Sie es in die spezielle Wortliste "gefunden". Die endgültige Programmausgabe ist das längste Wort in der gefundenen Liste.
Überprüfen Sie den Vorgang, indem Sie kopieren und kommentieren, während Sie auf den Bildschirm schauen. (Das ursprüngliche Antwortbeispiel muss den Einzug der if-Anweisung in Zeile 35 korrigieren.)
#!/usr/bin/env python
import collections
import sys
import logging
logging.basicConfig(level = logging.DEBUG, format = "%(asctime)s - %(levelname)s - %(message)s")
logging.disable(logging.DEBUG)
def find_longest_word_in_string(letters, words):
letter_positions = collections.defaultdict(list)
#So erstellen Sie eine Liste, für die keine Initialisierung erforderlich ist. Verwenden Sie defaultdict.
for index, letter in enumerate(letters):
letter_positions[letter].append(index)
#Extrahieren Sie Zeichen aus Buchstaben als Wörterbuchschlüssel.
#Speichern Sie die Position des Buchstabens in Buchstaben in einer Liste im Wörterbuch.
#Schlüssel ist Buchstabe.
for word in sorted(words, key=lambda w: len(w), reverse=True):
#Sortieren Sie Wörter in Wörtern in absteigender Reihenfolge nach Länge
pos = 0
for letter in word:
logging.debug("word is {}, letter is {}." .format(word, letter))
if letter not in letter_positions:
break
#Der Charakter ist Buchstabe_brechen, wenn nicht in Positionen
possible_positions = [p for p in letter_positions[letter] if p >= pos]
#p ist die Position des Zielbuchstabens. Selbst wenn die if-Anweisung in der Mitte der for-Schleife unterbrochen ist, wird pos hinzugefügt
#Das nächste Zeichen ist das Beurteilungsziel.
logging.debug("possible_positions are {}." .format(possible_positions))
logging.debug("pos is {}." .format(pos))
if not possible_positions:
break
logging.debug("possible_positions[0] is {}." .format(possible_positions[0]))
pos = possible_positions[0] + 1
#possible_positin[0]Gibt die erste Zahl in der Liste zurück, in der die Buchstabenposition gespeichert ist.
#Mit ↑ wird das in Buchstaben zu beurteilende Zeichen auf das Zeichen nach dem aktuellen Buchstaben gesetzt.
#Beispiel: Buchstaben= "aaapplle"、word = "apple"Im Falle von,
#Der Buchstabe der Schleife in der ersten Runde ist"a"Weil es möglich ist_positions = (0, 1, 2)
#Die Position der nächsten Schleife ist 0+ 1 = 1
#In der nächsten Schleife ist der Buchstabe"p"Weil es möglich ist_positions = (3, 4)
#Die Position der nächsten Schleife ist 3+ 1 = 4
#In der nächsten Schleife ist der Buchstabe"p"Aber p>=Weil die Bedingung 4 oder mehr als pos ist
#possible_positions = (4)
#Wenn das Wort abwechselnd keine Zeichen mehr enthält, wird es nicht unterbrochen und das Wort wird zurückgegeben.
else:
return word
#print(find_longest_word_in_string(sys.argv[1], sys.argv[2:]))
#Führen Sie dies aus, indem Sie eine Zeichenfolge und ein Wort in der Befehlszeile angeben.
if __name__ == '__main__':
letters = "abppplee"
words = ["able", "ale", "apple", "bale", "kangaroo"]
print(find_longest_word_in_string(letters, words))
#Wenn Sie die Skriptdatei direkt über die Befehlszeile ausführen,__name__Automatisch in der Variablen (Attribut)
# __main__Die "Ersatz" -Operation wird ganz am Anfang ausgeführt.
・ Es braucht Zeit, um die Anzahl der Zeichen x die Anzahl der Wörter, es ist langsam ・ Zumindest hätte ich nach Wortlänge sortieren und in der Mitte brechen sollen ・ Es ist wichtig, eine Datenvorverarbeitung zu entwickeln
Recommended Posts