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 ist, und zusätzlich zur Antwort O(1) Speicher. Der spaltenweise Durchlauf ist außerdem durch n × (L+1) begrenzt, wobei L die Länge der Antwort ist, sodass er vorzeitig abbricht, wenn die Wörter bereits am Anfang voneinander abweichen.

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

Die leere Zeichenfolge "" . 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 schlechtesten Fall, O(S) . Vertikales Scannen ist die sicherere Wahl: Es stoppt bei der ersten Spalte, in der ein Wort abweicht, während horizontales Scannen ein langes Präfix mit vielen Wörtern vergleichen kann, bevor ein spätes Wort es verkürzt.

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 ist die Antwort 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 gesamte Antwort. Ein gemeinsames Präfix kann niemals länger sein als das kürzeste Wort.

Weiterführende Frage

Angenommen, die Liste bleibt unverändert und viele Suchwörter treffen ein. Wie würdest du für jedes Suchwort das längste Präfix finden, das es mit einem Wort in der Liste gemeinsam hat, ohne die Liste 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 ihn jedes Wort an derselben Position hat. Die Antwort endet an der ersten Position, an der ein Wort abweicht oder keine weiteren Buchstaben mehr hat. Beide Ansätze lesen die Wörter Buchstabe für Buchstabe in einer anderen Reihenfolge. Beim Durchlaufen nach Spalten wird beim ersten Unterschied abgebrochen.

Verkleinere das Präfix Wort für Wort

Idee

Nimm an, das erste Wort ist vollständig die Antwort. Kürze es auf den Teil, den es mit dem zweiten Wort gemeinsam hat, dann mit dem dritten und so weiter. Der gemeinsame Präfix vieler Wörter ist der gemeinsame Präfix der ersten beiden, dann derjenige davon und des dritten Wortes: Bei jedem Schritt kann er nur beibehalten oder verkürzt werden. In Beispiel 1 geht der Kandidat beispielsweise nach dem zweiten Wort von interview zu inter über und bleibt dort.

Jeder Buchstabe wird höchstens einmal verglichen, daher beträgt die Laufzeit O(S) für insgesamt S Buchstaben. Die Schwachstelle ist die Reihenfolge: Bei 200 Wörtern mit jeweils 200 Buchstaben, bei denen sich nur das letzte Wort an seinem ersten Buchstaben unterscheidet, führst du fast 40.000 Vergleiche durch, 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 andere 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. Nimm den Buchstaben von strs[0] in der aktuellen Spalte und prüfe, ob jedes andere Wort dort denselben Buchstaben hat. Sobald ein Wort zum ersten Mal abweicht oder zu kurz ist, um diese Spalte zu haben, lautet die Antwort strs[0] bis zu dieser Spalte.

Die Antwort besteht genau aus der Folge von Spalten, in denen alle Wörter übereinstimmen, und diese Schleife durchläuft diese Folge von links und hält an, sobald sie unterbrochen wird. Wird sie nicht unterbrochen, ist strs[0] die Antwort.

Bei n Wörtern und einer Antwort der Länge L führt die Schleife höchstens n × (L+1) Prüfungen durch, was ebenfalls O(S) ist. Wenn sich nur das letzte von 200 Wörtern im ersten Buchstaben unterscheidet, hält sie nach 199 Vergleichen an.

Algorithmus

Sei first gleich strs[0].
Lies für jede Spalte col von 0 bis zur Länge von first minus eins first[col].
Wenn ein anderes Wort keinen Buchstaben an der Stelle col hat oder sein Buchstabe abweicht, gib 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

Über das Ende eines kürzeren Wortes hinaus lesen. In prefix, pre, prepare gibt es Spalte 3 in prefix, aber nicht in pre; prüfe die Länge, bevor du den Buchstaben ausliest.
Nur das erste und das letzte Wort vergleichen, ohne zu sortieren. In abc, xbd, abd haben diese beiden ab gemeinsam, aber xbd weicht in Spalte 0 ab, und die Antwort ist leer.
null oder einen Platzhalter zurückgeben, wenn nichts gemeinsam ist. Die Antwort ist die leere Zeichenkette.
Vergessen, dass ein einzelnes Wort sein eigenes Präfix ist: Allein gibt algorithm algorithm zurück.
Einer unveränderlichen Zeichenkette jeweils einen Buchstaben hinzufügen. Eine Antwort mit 200 Buchstaben verursacht dann 200 Kopien; speichere eine Länge und schneide das erste Wort 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 ist, und zusätzlich zur Antwort O(1) Speicher. Der spaltenweise Durchlauf ist außerdem durch n × (L+1) begrenzt, wobei L die Länge der Antwort ist, sodass er vorzeitig abbricht, wenn die Wörter bereits 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 mit dem, was diese beiden gemeinsam haben. Daher liefert der Vergleich nur dieser beiden die Antwort. Beim Sortieren werden etwa n log n Wortpaare verglichen, was mehr kostet als ein einziger Durchlauf, aber der Code ist kurz.

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

Die leere Zeichenfolge "". 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 schlechtesten Fall, O(S). Vertikales Scannen ist die sicherere Wahl: Es stoppt bei der ersten Spalte, in der ein Wort abweicht, während horizontales Scannen ein langes Präfix mit vielen Wörtern vergleichen kann, bevor ein spätes Wort es verkürzt.

def longestCommonPrefix(strs):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

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

Erwartete Ausgabe

"inter"