Longest Common Prefix

Q: Wie hoch ist die Zeitkomplexität des längsten gemeinsamen Präfixes?

Beide Durchläufe benötigen O(S) Zeit, wobei S die Gesamtzahl der Buchstaben in allen Wörtern ist, und benötigen neben der Antwort nur O(1) zusätzlichen Speicher. Der spaltenweise Durchlauf ist außerdem durch n × (L+1) begrenzt, wobei L die Länge der Antwort ist, sodass er frühzeitig abbricht, wenn die Wörter schon am Anfang voneinander abweichen.

Q: Was sollte Longest Common Prefix zurückgeben, wenn es kein gemeinsames Präfix gibt?

Es gibt die leere Zeichenfolge "" zurück. Das passiert, sobald zwei Wörter mit unterschiedlichen Buchstaben beginnen, wie bei stack , queue und heap .

Q: Was ist besser: horizontales oder vertikales Scannen?

Beide haben denselben Worst Case, O(S) . Das vertikale Scannen, Spalte für Spalte, ist die sicherere Wahl: Es stoppt bei der ersten Spalte, in der ein Wort abweicht, während beim horizontalen Scannen ein langes Präfix mit vielen Wörtern verglichen werden kann, bevor ein späteres Wort den Vergleich beendet.

LeichtArrays und Strings

+10

Du erhältst ein Array von Wörtern strs. Gib die längste Zeichenfolge zurück, mit der jedes Wort beginnt. Wenn nicht alle Wörter mit demselben Buchstaben beginnen, gib die leere Zeichenfolge "" zurück. Ein Wort gilt als Präfix seiner selbst, daher ist ein einzelnes Wort seine eigene Antwort.

Funktion

longestCommonPrefix(strs: string-array) → string

strsstring-array: die zu vergleichenden Wörter
Gibt zurückstring: das längste Präfix, das alle Wörter gemeinsam haben, oder eine leere Zeichenfolge

Einschränkungen

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
Jedes Wort enthält ausschließlich englische Kleinbuchstaben.

Beispiele

Eingabe: strs = ["interview", "internet", "interval", "internal"]
Ausgabe: "inter"
Erklärung: Alle vier Wörter beginnen mit inter. An der nächsten Stelle haben interview und interval ein v, internet und internal ein n, daher endet das Präfix dort.

Eingabe: strs = ["stack", "queue", "heap"]
Ausgabe: ""
Erklärung: Die Wörter beginnen mit s, q und h. Sie unterscheiden sich bereits im ersten Buchstaben, daher haben sie kein gemeinsames Präfix und die Antwort ist leer.

Eingabe: strs = ["prefix", "pre", "prepare"]
Ausgabe: "pre"
Erklärung: pre ist das kürzeste Wort und die beiden anderen beginnen damit, also ist es die ganze Antwort. Ein gemeinsames Präfix kann niemals länger als das kürzeste Wort sein.

+19 versteckte Tests beim Einreichen

Weiterführende Frage

Angenommen, die Liste bleibt unverändert und du erhältst viele Suchwörter. Wie würdest du für jede Suchanfrage das längste Präfix finden, das sie mit mindestens einem Wort in der Liste gemeinsam hat, ohne die Liste jedes Mal erneut zu durchsuchen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Ein Buchstabe gehört nur dann zur Antwort, wenn jedes Wort an derselben Position denselben Buchstaben hat. Die Antwort endet an der ersten Position, an der sich ein Wort unterscheidet oder kein Buchstabe mehr vorhanden ist. Beide Ansätze unten lesen die Wörter Buchstabe für Buchstabe; sie unterscheiden sich in der Reihenfolge, in der sie die Buchstaben lesen. Beim spaltenweisen Durchgehen wird beim ersten Unterschied abgebrochen, sodass nie weiter als bis zur Antwort plus einer Spalte gelesen wird.

Das Präfix Wort für Wort verkürzen

Idee

Gehe zunächst davon aus, dass das ganze erste Wort die Antwort ist. Vergleiche es dann Buchstabe für Buchstabe mit dem zweiten Wort und kürze es auf den gemeinsamen Teil. Vergleiche den verbleibenden Teil mit dem dritten Wort und so weiter. Nach dem letzten Wort ist das übrig, was allen gemeinsam ist.

Das ist korrekt, weil der gemeinsame Präfix vieler Wörter der gemeinsame Präfix der ersten beiden Wörter ist, dann der gemeinsame Präfix dieses Ergebnisses und des dritten Wortes und so weiter: Bei jedem Schritt kann er nur beibehalten oder verkürzt werden. Bei interview, internet, interval, internal wird der Kandidat nach dem zweiten Wort von interview zu inter und bleibt dort.

Jeder Buchstabe wird höchstens einmal verglichen, daher beträgt die Laufzeit O(S), wobei S die Gesamtzahl der Buchstaben ist. Du speicherst nur eine Länge, keine Kopie. Die Schwachstelle ist die Reihenfolge: Bei 200 Wörtern mit jeweils 200 Buchstaben, bei denen die ersten 199 Wörter übereinstimmen und sich nur das letzte an seinem ersten Buchstaben unterscheidet, vergleichst du jeden der 200 Buchstaben mit jedem der ersten 199 Wörter, also fast 40.000 Vergleiche, bevor das letzte Wort den Präfix auf nichts kürzt.

Algorithmus

Setze prefixLen auf die Länge von strs[0].
Zähle für jedes weitere Wort, wie viele Anfangsbuchstaben es mit strs[0] gemeinsam hat, bis zu prefixLen.
Setze prefixLen auf diese Anzahl und brich vorzeitig ab, wenn sie 0 erreicht.
Gib die ersten prefixLen Buchstaben von strs[0] zurück.

def longestCommonPrefix(strs):
    first = strs[0]
    prefix_len = len(first)
    for word in strs[1:]:
        common = 0
        while common < prefix_len and common < len(word) and word[common] == first[common]:
            common += 1
        prefix_len = common
        if prefix_len == 0:
            break
    return first[:prefix_len]

Spalte für Spalte vergleichen

Idee

Lies die Wörter wie eine Tabelle, eine Spalte nach der anderen. Spalte 0 enthält den ersten Buchstaben jedes Wortes, Spalte 1 den zweiten und so weiter. Nimm den Buchstaben von strs[0] in der aktuellen Spalte und prüfe, ob alle anderen Wörter dort denselben Buchstaben haben. Sobald ein Wort abweicht oder zu kurz ist, um diese Spalte überhaupt zu haben, lautet die Antwort strs[0] bis zu dieser Spalte.

Die Antwort ist genau die Folge von Spalten, in denen alle Wörter übereinstimmen, und diese Schleife durchläuft die Spalten von links und hält bei der ersten an, die diese Folge unterbricht. Wenn keine Spalte sie unterbricht, ist strs[0] selbst die Antwort; es ist dann das kürzeste Wort oder gleich lang wie dieses.

Die Schleife liest höchstens eine Spalte hinter der Antwort, sodass sie bei n Wörtern und einer Antwort der Länge L höchstens n × (L+1) Prüfungen durchführt. Außerdem liest sie denselben Buchstaben eines Wortes nie zweimal, ist also auch O(S). Im obigen Fall, in dem 199 Wörter übereinstimmen und das letzte Wort bereits beim ersten Buchstaben abweicht, hält sie nach der ersten Spalte an: 199 Vergleiche statt fast 40.000.

Algorithmus

Sei first gleich strs[0].
Lies für jede Spalte col von 0 bis zur Länge von first minus eins first[col].
Gib für jedes andere Wort, falls es an col keinen Buchstaben hat oder sich sein Buchstabe unterscheidet, die ersten col Buchstaben von first zurück.
Wenn alle Spalten übereinstimmen, gib first zurück.

def longestCommonPrefix(strs):
    first = strs[0]
    for col in range(len(first)):
        for word in strs[1:]:
            if col == len(word) or word[col] != first[col]:
                return first[:col]
    return first

Stolperfallen und Grenzfälle

Die Antwort ist kurz, und die Fehler stecken am Ende.

Über das Ende eines kürzeren Wortes hinauslesen. In prefix, pre, prepare gibt es Spalte 3 in prefix, aber nicht in pre; prüfe die Länge, bevor du den Buchstaben liest.
Nur das erste und das letzte Wort in der gegebenen Reihenfolge vergleichen. Diese Abkürzung setzt voraus, dass die Wörter zuerst sortiert werden: In abc, xbd, abd haben das erste und das letzte Wort ab gemeinsam, aber xbd bricht Spalte 0, und die Antwort ist leer.
null oder einen Platzhalter zurückgeben, wenn nichts gemeinsam ist. Die Antwort ist die leere Zeichenfolge.
Vergessen, dass ein einzelnes Wort sein eigenes Präfix ist: algorithm allein gibt algorithm zurück.
Die Antwort bilden, indem du einem unveränderlichen String Buchstabe für Buchstabe hinzufügst. Bei einer Antwort mit 200 Buchstaben sind das 200 Kopien; speichere eine Länge und schneide das erste Wort am Ende einmal zu.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität des längsten gemeinsamen Präfixes?

Beide Durchläufe benötigen O(S) Zeit, wobei S die Gesamtzahl der Buchstaben in allen Wörtern ist, und benötigen neben der Antwort nur O(1) zusätzlichen Speicher. Der spaltenweise Durchlauf ist außerdem durch n × (L+1) begrenzt, wobei L die Länge der Antwort ist, sodass er frühzeitig abbricht, wenn die Wörter schon am Anfang voneinander abweichen.

Kannst du das längste gemeinsame Präfix finden, indem du die Wörter sortierst?

Ja. In alphabetischer Reihenfolge beginnt jedes Wort zwischen dem ersten und dem letzten Wort mit dem, was diese beiden gemeinsam haben. Daher liefert der Vergleich nur des ersten und des letzten Wortes die Antwort. Die Sortierung vergleicht etwa n log n Wortpaare, was mehr kostet als ein einziger Durchlauf, aber der Code ist kurz.

Was sollte Longest Common Prefix zurückgeben, wenn es kein gemeinsames Präfix gibt?

Es gibt die leere Zeichenfolge "" zurück. Das passiert, sobald zwei Wörter mit unterschiedlichen Buchstaben beginnen, wie bei stack, queue und heap.

Was ist besser: horizontales oder vertikales Scannen?

Beide haben denselben Worst Case, O(S). Das vertikale Scannen, Spalte für Spalte, ist die sicherere Wahl: Es stoppt bei der ersten Spalte, in der ein Wort abweicht, während beim horizontalen Scannen ein langes Präfix mit vielen Wörtern verglichen werden kann, bevor ein späteres Wort den Vergleich beendet.

Python

def longestCommonPrefix(strs):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

strs = ["interview", "internet", "interval", "internal"]

Erwartet

"inter"