Longest Common Prefix

Q: Jaka jest złożoność czasowa problemu najdłuższego wspólnego prefiksu?

Oba skanowania działają w czasie O(S) , gdzie S to łączna liczba liter we wszystkich słowach, i wymagają tylko O(1) dodatkowej pamięci poza odpowiedzią. Skanowanie kolumnami jest również ograniczone przez n × (L+1) , gdzie L to długość odpowiedzi, więc kończy się wcześniej, gdy słowa różnią się już na początku.

Q: Co powinna zwrócić najdłuższy wspólny prefiks, gdy nie ma wspólnego prefiksu?

Zwraca pusty ciąg "" . Dzieje się tak, gdy tylko dwa słowa zaczynają się od różnych liter, jak w przypadku stack , queue i heap .

Q: Które skanowanie jest lepsze: poziome czy pionowe?

Obie metody mają taki sam pesymistyczny przypadek: O(S) . Bezpieczniejszym wyborem jest skanowanie pionowe, kolumna po kolumnie: zatrzymuje się przy pierwszej kolumnie, w której któreś słowo się różni, podczas gdy skanowanie poziome może porównywać długi prefiks z wieloma słowami, zanim jedno z późniejszych słów go skróci.

ŁatweTablice i napisy

+10

Otrzymujesz tablicę słów strs. Zwróć najdłuższy ciąg znaków, od którego zaczyna się każde słowo. Jeśli nie wszystkie słowa zaczynają się na tę samą literę, zwróć pusty ciąg "". Słowo jest swoim własnym prefiksem, więc w przypadku jednego słowa odpowiedzią jest ono samo.

Funkcja

longestCommonPrefix(strs: string-array) → string

strsstring-array: słowa do porównania
Zwracastring: najdłuższy prefiks wspólny dla wszystkich słów albo pusty ciąg

Ograniczenia

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
Każde słowo zawiera wyłącznie małe litery alfabetu angielskiego.

Przykłady

Wejście: strs = ["interview", "internet", "interval", "internal"]
Wyjście: "inter"
Wyjaśnienie: Wszystkie cztery słowa zaczynają się od inter. Na następnej pozycji w słowach interview i interval występuje v, a w słowach internet i internal — n, więc prefiks kończy się w tym miejscu.

Wejście: strs = ["stack", "queue", "heap"]
Wyjście: ""
Wyjaśnienie: Słowa zaczynają się od s, q i h. Różnią się już pierwszą literą, więc nie mają wspólnego prefiksu, a odpowiedź jest pusta.

Wejście: strs = ["prefix", "pre", "prepare"]
Wyjście: "pre"
Wyjaśnienie: pre to najkrótsze słowo, a dwa pozostałe zaczynają się od niego, więc jest to cała odpowiedź. Wspólny prefiks nigdy nie może być dłuższy niż najkrótsze słowo.

+19 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Załóżmy, że lista pozostaje niezmienna, a Ty otrzymujesz wiele słów zapytania. Jak znaleźć dla każdego zapytania najdłuższy prefiks wspólny z co najmniej jednym słowem z listy, nie przeszukując za każdym razem ponownie całej listy?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Litera należy do odpowiedzi tylko wtedy, gdy każde słowo ma tę samą literę na tej samej pozycji, a odpowiedź kończy się na pierwszej pozycji, na której którekolwiek słowo się różni lub się kończy. Oba poniższe podejścia odczytują słowa litera po literze; różnią się kolejnością ich odczytywania. Skanowanie kolumnami zatrzymuje się przy pierwszej niezgodności, więc nigdy nie odczytuje więcej niż odpowiedź plus jedna kolumna.

Zmniejszaj prefiks słowo po słowie

Intuicja

Zacznij od założenia, że całe pierwsze słowo jest odpowiedzią. Następnie porównuj je z drugim słowem, litera po literze, i skracaj do wspólnej części. Porównaj to, co zostało, z trzecim słowem i tak dalej. Po ostatnim słowie pozostanie część wspólna dla wszystkich.

To poprawne, ponieważ wspólny prefiks wielu słów to wspólny prefiks pierwszych dwóch słów, a następnie wspólny prefiks tego wyniku i trzeciego słowa, i tak dalej: każdy krok może go jedynie zachować albo skrócić. Dla interview, internet, interval, internal kandydat zmienia się z interview na inter po drugim słowie i pozostaje taki sam.

Każda litera jest porównywana najwyżej raz, więc złożoność czasowa wynosi O(S), gdzie S to łączna liczba liter. Przechowujesz tylko długość, a nie kopię. Słabym punktem jest kolejność: mając 200 słów po 200 liter, z których pierwsze 199 jest zgodnych, a dopiero pierwsza litera ostatniego słowa jest inna, porównujesz wszystkie 200 liter z każdym z pierwszych 199 słów — prawie 40 000 porównań — zanim ostatnie słowo skróci prefiks do zera.

Algorytm

Ustaw prefixLen na długość strs[0].
Dla każdego pozostałego słowa policz, ile początkowych liter ma wspólnych z strs[0], maksymalnie do prefixLen.
Ustaw prefixLen na tę liczbę i zakończ wcześniej, jeśli osiągnie 0.
Zwróć pierwsze prefixLen liter z strs[0].

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]

Porównuj kolumna po kolumnie

Intuicja

Czytaj słowa jak tabelę, po jednej kolumnie naraz. Kolumna 0 zawiera pierwszą literę każdego słowa, kolumna 1 — drugą i tak dalej. Weź literę z strs[0] w bieżącej kolumnie i sprawdź, czy każde pozostałe słowo ma w niej tę samą literę. Gdy po raz pierwszy któreś słowo się nie zgodzi albo będzie zbyt krótkie, by w ogóle mieć tę kolumnę, odpowiedzią jest strs[0] aż do tej kolumny.

Odpowiedź to dokładnie ciąg kolumn, w których wszystkie słowa są zgodne, a ta pętla przechodzi przez te kolumny od lewej strony i zatrzymuje się na pierwszej, która przerywa ten ciąg. Jeśli żadna kolumna go nie przerwie, odpowiedzią jest samo strs[0]; jest wtedy najkrótszym słowem albo ma taką samą długość jak ono.

Pętla odczytuje najwyżej jedną kolumnę poza odpowiedzią, więc przy n słowach i odpowiedzi o długości L wykonuje co najwyżej n × (L+1) sprawdzeń. Ponadto nigdy nie odczytuje dwa razy tej samej litery słowa, więc jej złożoność wynosi również O(S). W opisanym wyżej przypadku, gdy 199 słów jest zgodnych, a pierwsza litera ostatniego słowa jest inna, pętla zatrzymuje się po pierwszej kolumnie: wykonuje 199 porównań zamiast prawie 40 000.

Algorytm

Niech first będzie równe strs[0].
Dla każdej kolumny col od 0 do długości first minus jeden odczytaj first[col].
Dla każdego pozostałego słowa, jeśli nie ma ono litery na pozycji col lub jego litera jest inna, zwróć pierwsze col liter ciągu first.
Jeśli wszystkie kolumny są zgodne, zwróć first.

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

Pułapki i przypadki brzegowe

Odpowiedź jest krótka, a błędy czają się na jej końcu.

Odczytywanie znaków poza końcem krótszego wyrazu. W prefix, pre, prepare kolumna 3 istnieje w prefix, ale nie w pre; sprawdź długość, zanim odczytasz literę.
Porównywanie tylko pierwszego i ostatniego wyrazu w podanej kolejności. Ten skrót wymaga wcześniejszego posortowania wyrazów: w abc, xbd, abd pierwszy i ostatni mają wspólne ab, ale xbd nie pasuje w kolumnie 0, więc odpowiedzią jest pusty ciąg.
Zwracanie null lub wartości zastępczej, gdy nic nie jest wspólne. Odpowiedzią jest pusty ciąg.
Zapominanie, że pojedynczy wyraz jest swoim własnym prefiksem: samo algorithm zwraca algorithm.
Budowanie odpowiedzi przez dodawanie po jednej literze do niezmiennego ciągu. Odpowiedź o długości 200 liter oznacza 200 kopii; przechowuj długość i na końcu przytnij pierwszy wyraz tylko raz.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu najdłuższego wspólnego prefiksu?

Oba skanowania działają w czasie O(S), gdzie S to łączna liczba liter we wszystkich słowach, i wymagają tylko O(1) dodatkowej pamięci poza odpowiedzią. Skanowanie kolumnami jest również ograniczone przez n × (L+1), gdzie L to długość odpowiedzi, więc kończy się wcześniej, gdy słowa różnią się już na początku.

Czy potrafisz znaleźć najdłuższy wspólny prefiks, sortując słowa?

Tak. W porządku alfabetycznym każde słowo między pierwszym a ostatnim zaczyna się od tego, co mają one wspólnego, więc porównanie tylko pierwszego i ostatniego słowa daje odpowiedź. Sortowanie porównuje około n log n par słów, co kosztuje więcej niż jedno przejście, ale kod jest krótki.

Co powinna zwrócić najdłuższy wspólny prefiks, gdy nie ma wspólnego prefiksu?

Zwraca pusty ciąg "". Dzieje się tak, gdy tylko dwa słowa zaczynają się od różnych liter, jak w przypadku stack, queue i heap.

Które skanowanie jest lepsze: poziome czy pionowe?

Obie metody mają taki sam pesymistyczny przypadek: O(S). Bezpieczniejszym wyborem jest skanowanie pionowe, kolumna po kolumnie: zatrzymuje się przy pierwszej kolumnie, w której któreś słowo się różni, podczas gdy skanowanie poziome może porównywać długi prefiks z wieloma słowami, zanim jedno z późniejszych słów go skróci.

Python

def longestCommonPrefix(strs):
    # Napisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

"inter"