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, i wymagają O(1) dodatkowej pamięci poza odpowiedzią. Skanowanie kolumn jest również ograniczone przez n × (L+1) dla odpowiedzi o długości L , więc kończy się wcześniej, gdy słowa różnią się już na początku.

Q: Co powinna zwracać funkcja Longest Common Prefix, gdy nie ma wspólnego prefiksu?

Pusty ciąg znaków "" . 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 przypadek najgorszy: O(S) . Skanowanie pionowe jest bezpieczniejszym wyborem: zatrzymuje się przy pierwszej kolumnie, w której dowolne słowo się różni, podczas gdy skanowanie poziome może porównywać długi prefiks z wieloma słowami, zanim późne słowo 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 słowa nie zaczynają się tą samą literą, zwróć pusty ciąg znaków "". Słowo jest swoim własnym prefiksem, więc gdy podano jedno słowo, jest ono odpowiedzią.

Funkcja

longestCommonPrefix(strs: string-array) → string

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

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 kolejnej 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 odpowiedź jest pusta.

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

Pytanie dodatkowe

Załóżmy, że lista pozostaje niezmienna, a pojawia się wiele zapytań o słowa. Jak znaleźć najdłuższy prefiks każdego zapytania wspólny z którymś słowem z listy, bez ponownego przeszukiwania 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 ją na tej samej pozycji. Odpowiedź kończy się na pierwszej pozycji, na której słowo się nie zgadza lub się kończy. Oba podejścia odczytują słowa litera po literze, ale w innej kolejności. Skanowanie kolumnami kończy się na pierwszej niezgodności.

Zmniejszaj prefiks słowo po słowie

Intuicja

Załóż, że całe pierwsze słowo jest odpowiedzią. Skróć je do części wspólnej z drugim słowem, potem z trzecim i tak dalej. Wspólny prefiks wielu słów to wspólny prefiks pierwszych dwóch, a następnie tego wyniku i trzeciego słowa: każdy krok może go tylko zachować lub skrócić. Na przykładzie 1 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 czas działania wynosi O(S) dla S liter łącznie. Słabym punktem jest kolejność: przy 200 słowach po 200 liter, gdy tylko ostatnie słowo różni się pierwszą literą, wykonujesz blisko 40 000 porównań, zanim ostatnie słowo skróci prefiks do pustego ciągu.

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 przerwij 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ównaj kolumnę po kolumnie

Intuicja

Czytaj słowa jak tabelę, kolumna po kolumnie. Weź literę z strs[0] w bieżącej kolumnie i sprawdź, czy każde inne słowo ma tam tę samą literę. Gdy tylko któreś słowo się nie zgodzi lub będzie zbyt krótkie, by zawierać tę kolumnę, odpowiedzią jest strs[0] do tej kolumny.

Odpowiedź to dokładnie ciąg kolumn, w których zgadzają się wszystkie słowa, a ta pętla przechodzi przez ten ciąg od lewej strony i zatrzymuje się w miejscu, w którym zgodność się kończy. Jeśli nic jej nie przerwie, odpowiedzią jest strs[0].

Dla n słów i odpowiedzi o długości L pętla wykonuje najwyżej n × (L+1) sprawdzeń, co odpowiada również O(S). W przypadku, gdy różni się tylko ostatnie z 200 słów i to już jego pierwsza litera, pętla zatrzymuje się po 199 porównaniach.

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 innego słowa, jeśli nie ma litery na pozycji col lub jego litera jest inna, zwróć pierwsze col liter z 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

Odczytywanie znaków poza końcem krótszego słowa. W prefix, pre, prepare kolumna 3 istnieje w prefix, ale nie w pre; przed odczytaniem znaku sprawdź długość.
Porównywanie tylko pierwszego i ostatniego słowa bez sortowania. W abc, xbd, abd te dwa słowa mają wspólne ab, ale xbd nie pasuje w kolumnie 0, więc wynikiem jest pusty ciąg.
Zwracanie null lub wartości zastępczej, gdy nic nie jest wspólne. Wynikiem jest pusty ciąg.
Zapominanie, że pojedyncze słowo jest swoim własnym prefiksem: samo algorithm zwraca algorithm.
Dodawanie po jednej literze do niezmiennego ciągu. Odpowiedź o długości 200 liter wymaga wtedy 200 kopii; zachowaj długość i raz wytnij fragment z pierwszego słowa.

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, i wymagają O(1) dodatkowej pamięci poza odpowiedzią. Skanowanie kolumn jest również ograniczone przez n × (L+1) dla odpowiedzi o długości L, 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 kolejności alfabetycznej każde słowo między pierwszym a ostatnim zaczyna się od tego, co łączy te dwa słowa, więc porównanie tylko tych dwóch 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 zwracać funkcja Longest Common Prefix, gdy nie ma wspólnego prefiksu?

Pusty ciąg znaków "". 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 przypadek najgorszy: O(S). Skanowanie pionowe jest bezpieczniejszym wyborem: zatrzymuje się przy pierwszej kolumnie, w której dowolne słowo się różni, podczas gdy skanowanie poziome może porównywać długi prefiks z wieloma słowami, zanim późne słowo go skróci.

def longestCommonPrefix(strs):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik

"inter"