Edit Distance

Q: Jaka jest złożoność czasowa odległości edycyjnej?

Rozwiązanie z tabelą działa w czasie O(n × m) , gdzie n i m to długości dwóch ciągów, ponieważ wypełnia jedną komórkę dla każdej pary prefiksów, wykonując stałą liczbę operacji. Pełna tabela wymaga O(n × m) pamięci, a tabela złożona z dwóch wierszy — O(min(n, m)) . Zwykła rekurencja bez tabeli ma złożoność wykładniczą.

Q: Jak uzyskać listę zmian, a nie tylko ich liczbę?

Zachowaj całą tablicę i cofaj się od dp[n][m] . Jeśli litery są takie same, przejdź po przekątnej bez edycji. W przeciwnym razie przejdź do sąsiedniej komórki o wartości mniejszej o jeden: ruch po przekątnej oznacza zastąpienie, w górę — usunięcie, w lewo — wstawienie. Zatrzymaj się przy dp[0][0] i odczytaj edycje w odwrotnej kolejności. Wersja z dwoma wierszami nie może tego zrobić samodzielnie, ponieważ odrzuciła wcześniejsze wiersze.

Q: Czy odległość edycyjna może być obliczona za pomocą jednej tablicy?

Tak. Wypełnij jedną tablicę row w miejscu, od lewej do prawej. Zanim nadpiszesz row[j] , nadal zawiera ono wartość z poprzedniego wiersza, a row[j-1] zawiera już wartość z bieżącego wiersza. Jedyną wartością, którą tracisz, jest wartość po przekątnej, więc zachowaj ją w zmiennej: zapisz starą wartość row[j] przed zapisaniem nowej i użyj jej jako wartości po przekątnej dla j + 1 .

TrudneProgramowanie dynamiczne

+10

Otrzymujesz dwa słowa: word1 i word2. Jedna edycja zmienia word1 na jeden z trzech sposobów: wstawia literę w dowolnym miejscu, usuwa literę lub zastępuje literę inną. Zwróć najmniejszą liczbę edycji potrzebnych do przekształcenia word1 w word2.

Funkcja

minDistance(word1: string, word2: string) → integer

word1string: edytowane przez Ciebie słowo
word2string: wyraz do osiągnięcia
Zwracainteger: najmniejsza liczba wstawień, usunięć i zamian, które przekształcają word1 w word2

Ograniczenia

1 ≤ word1.length ≤ 500
1 ≤ word2.length ≤ 500
Oba słowa zawierają wyłącznie małe litery alfabetu angielskiego.

Przykłady

Wejście: word1 = "spot"word2 = "stop"
Wyjście: 2
Wyjaśnienie: Zamień p na t, a t na p: spot zmienia się w stot, a następnie w stop. Jedna zmiana nie wystarczy, ponieważ te słowa różnią się w dwóch miejscach, a wstawienie lub usunięcie zmieniłoby ich długość.

Wejście: word1 = "garden"word2 = "ardent"
Wyjście: 2
Wyjaśnienie: Usuń g, aby otrzymać arden, a następnie wstaw t na końcu, aby otrzymać ardent. Zastępowanie liter jedna po drugiej kosztowałoby 6, ponieważ te dwa słowa różnią się na każdej pozycji.

Wejście: word1 = "rain"word2 = "shine"
Wyjście: 3
Wyjaśnienie: Zamień r na s, a a na h, aby otrzymać shin, a następnie wstaw e. Nie da się tego zrobić w dwóch edycjach: r ani a nie występują w shine, więc każda z nich wymaga edycji, która nie wydłuża słowa, a słowo nadal musi zyskać jedną literę.

+21 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz też zwrócić jedną najkrótszą listę zmian, a nie tylko podać, ile ich jest?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Edycje oddziałują na siebie, więc nie możesz poprawiać słów pozycja po pozycji: garden i ardent różnią się na wszystkich sześciu pozycjach, a jednak wystarczą dwie edycje, gdy usuniesz g i wszystko przesunie się w lewo. Pomysł, który pozwala to rozwiązać, polega na przyjrzeniu się tylko ostatniej literze każdego słowa. Albo te dwie litery już są takie same, albo jedna z dokładnie trzech edycji sprawi, że będą takie same, a każdy wybór pozostawia ten sam problem dla krótszych prefiksów. Tabela odpowiedzi o wymiarach (n+1) × (m+1) rozwiązuje wszystkie pary prefiksów naraz, a wystarczą z niej dwa wiersze.

Wypróbuj wszystkie trzy edycje z rekurencją

Poprawne, ale nie kończy się na największych testach

Intuicja

Niech edits(i, j) oznacza najmniejszą liczbę edycji potrzebną do przekształcenia sufiksu word1[i:] w word2[j:]. Przyjrzyj się pierwszym literom obu sufiksów. Jeśli są takie same, zachowaj je i przesuń oba indeksy: zgodna litera nigdy nie wymaga edycji, a każdy plan, który poświęca na nią edycję, można zmienić na taki, który ją zachowuje, bez zwiększania liczby edycji.

Jeśli są różne, jakaś edycja musi dotyczyć word1[i] lub utworzyć word2[j], a są dokładnie trzy możliwości. Zastąp word1[i] przez word2[j] i przesuń oba indeksy: edits(i+1, j+1). Usuń word1[i] i przesuń tylko i: edits(i+1, j). Wstaw word2[j] przed nim i przesuń tylko j: edits(i, j+1). Odpowiedź to 1 plus najmniejszy koszt z tych trzech możliwości. Gdy w word1 skończą się litery, wstaw pozostałą część word2, co kosztuje m - j; gdy w word2 skończą się litery, usuń pozostałą część word1, co kosztuje n - i.

Działa to wolno, ponieważ przy każdej różnicy uruchamiane są trzy wywołania. Dla dwóch słów składających się z 15 liter, bez żadnej wspólnej litery, daje to około 6.7 × 10^10 wywołań, a duże testy zawierają po 500 liter. Istnieje jednak tylko (n+1) × (m+1) różnych par (i, j), więc niemal każde wywołanie powtarza wcześniejsze.

Algorytm

Napisz funkcję edits(i, j) dla sufiksów zaczynających się na pozycjach i i j.
Jeśli i wykracza poza koniec word1, zwróć m - j; jeśli j wykracza poza koniec word2, zwróć n - i.
Jeśli word1[i] == word2[j], zwróć edits(i+1, j+1).
W przeciwnym razie zwróć 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)) dla zastąpienia, usunięcia i wstawienia.
Wynikiem jest edits(0, 0).

def minDistance(word1, word2):
    n, m = len(word1), len(word2)

    def edits(i, j):
        # Fewest edits to turn word1[i:] into word2[j:]
        if i == n:
            return m - j  # insert the rest of word2
        if j == m:
            return n - i  # delete the rest of word1
        if word1[i] == word2[j]:
            return edits(i + 1, j + 1)
        return 1 + min(edits(i + 1, j + 1),  # replace word1[i] with word2[j]
                       edits(i + 1, j),      # delete word1[i]
                       edits(i, j + 1))      # insert word2[j]

    return edits(0, 0)

Uzupełnij tabelę przedrostków

Intuicja

Stan. Niech dp[i][j] oznacza najmniejszą liczbę edycji potrzebnych do przekształcenia pierwszych i liter ciągu word1 w pierwsze j liter ciągu word2. Indeks 0 oznacza pusty prefiks.

Przejścia. Porównaj ostatnie litery obu prefiksów: word1[i-1] i word2[j-1]. Jeśli są równe, pozostaw je bez zmian: dp[i][j] = dp[i-1][j-1], czyli komórka położona ukośnie w górę i w lewo. Jeśli nie są równe, wykonaj jedną edycję i wybierz najtańszą z trzech sąsiednich komórek. Komórka po przekątnej, dp[i-1][j-1], oznacza zastąpienie word1[i-1] przez word2[j-1]. Komórka powyżej, dp[i-1][j], oznacza usunięcie word1[i-1]. Komórka po lewej, dp[i][j-1], oznacza wstawienie word2[j-1] na końcu.

Wiersz i kolumna bazowa. W przeciwieństwie do wielu problemów z tabelą nie zawierają zer. Przekształcenie i liter w pusty prefiks wymaga i usunięć, więc dp[i][0] = i. Utworzenie j liter od zera wymaga j wstawień, więc dp[0][j] = j. Każda komórka odczytuje komórkę powyżej, tę po lewej i komórkę po przekątnej, więc wypełnianie wierszami, od lewej do prawej, zapewnia, że są już obliczone. Odpowiedzią jest dp[n][m].

Oto tabela dla przekształcenia spot w stop, z kolumnami odpowiadającymi prefiksom "", s, st, sto, stop. Wiersz "" to [0, 1, 2, 3, 4], wiersz s to [1, 0, 1, 2, 3], wiersz sp to [2, 1, 1, 2, 2], wiersz spo to [3, 2, 2, 1, 2], a wiersz spot to [4, 3, 2, 2, 2]. Przyjrzyjmy się kilku komórkom. s i s są zgodne, więc komórka kopiuje wartość 0 z komórki po przekątnej. sp i st nie są zgodne: sąsiednie komórki mają wartości 0 po przekątnej, 1 powyżej i 1 po lewej, więc wynik to 1 + 0 = 1, czyli jedno zastąpienie. spo i sto są zgodne na literze o, więc komórka kopiuje wartość 1. W ostatniej komórce, dla spot i stop, porównujemy t z p: sąsiednie komórki mają wartości 1, 2 i 2, więc odpowiedź wynosi 1 + 1 = 2.

Tabela ma (n+1) × (m+1) komórek, a obliczenie każdej z nich wymaga stałej liczby operacji — około 2.5 × 10^5 kroków dla dwóch słów o długości 500 liter. Rekurencja z memoizacją wypełnia te same komórki, ale może osiągnąć głębokość n + m wywołań, co przekracza domyślny limit Pythona wynoszący 1000.

Algorytm

Utwórz tabelę dp zawierającą (n+1) × (m+1) komórek.
Ustaw dp[i][0] = i dla każdego i oraz dp[0][j] = j dla każdego j.
Dla i od 1 do n i j od 1 do m, jeśli word1[i-1] == word2[j-1], ustaw dp[i][j] = dp[i-1][j-1].
W przeciwnym razie ustaw dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
Zwróć dp[n][m].

def minDistance(word1, word2):
    n, m = len(word1), len(word2)
    # dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i  # delete all i letters
    for j in range(m + 1):
        dp[0][j] = j  # insert all j letters
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],  # replace
                                   dp[i - 1][j],      # delete word1[i-1]
                                   dp[i][j - 1])      # insert word2[j-1]
    return dp[n][m]

Zachowaj tylko dwa wiersze

Intuicja

Wiersz i odczytuje tylko wiersz i-1 i własne komórki po lewej stronie. Gdy wiersz jest gotowy, wiersze powyżej niego nie są już nigdy odczytywane. Użyj dwóch tablic: prev dla ukończonego wiersza i cur dla wiersza, który wypełniasz, a po każdym wierszu zamień je miejscami. Przejścia się nie zmieniają: przekątna to prev[j-1], komórka powyżej to prev[j], a komórka po lewej to cur[j-1].

Kolumna bazowa nie znika. Znajduje się teraz w pierwszym elemencie każdego wiersza, więc ustaw cur[0] = i przed wypełnieniem wiersza i. Wiersz 0 zaczyna się jako [0, 1, 2, ..., m], czyli wiersz bazowy.

Przekształcenie word2 w word1 wymaga takiej samej liczby edycji, ponieważ każde wstawienie staje się usunięciem, a każde usunięcie — wstawieniem. Możesz więc zamienić słowa miejscami i prowadzić wiersze wzdłuż krótszego z nich. Każdy wiersz zawiera wtedy min(n, m) + 1 liczb zamiast tabeli o maksymalnie 251,001 komórkach, a złożoność pracy pozostaje równa O(n × m).

Algorytm

Jeśli word2 jest dłuższe niż word1, zamień je miejscami.
Ustaw prev = [0, 1, ..., m], gdzie m to krótsza długość.
Dla każdego i od 1 do n ustaw cur[0] = i, a następnie wypełnij cur[1..m] według tej samej zasady, odczytując wartość po przekątnej i powyżej z prev, a z lewej z cur.
Zamień prev i cur miejscami.
Zwróć prev[m].

def minDistance(word1, word2):
    if len(word2) > len(word1):
        word1, word2 = word2, word1  # the rows run along the shorter word
    m = len(word2)
    # prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
    prev = list(range(m + 1))
    for i in range(1, len(word1) + 1):
        cur = [i] + [0] * m  # i letters into an empty prefix: delete them all
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j - 1],  # replace
                                 prev[j],      # delete word1[i-1]
                                 cur[j - 1])   # insert word2[j-1]
        prev = cur
    return prev[m]

Pułapki i przypadki brzegowe

Rekurencja jest krótka, więc większość błędów dotyczy przypadków bazowych lub tego, który sąsiad jest odczytywany.

Wypełnianie wiersza 0 i kolumny 0 zerami, tak jak w najdłuższym wspólnym podciągu. Zamiana abc na pusty prefiks kosztuje 3 usunięcia, a nie 0, więc dp[i][0] musi mieć wartość i, a dp[0][j] musi mieć wartość j.
Zapominanie o cur[0] = i w wersji z dwoma wierszami. Pierwszy element zachowuje wartość sprzed dwóch wierszy, a każda komórka za nim ma nieprawidłową wartość.
Dodawanie kosztu edycji przy dopasowaniu. dp[i][j] = 1 + min(...) dla jednakowych liter sprawia, że zamiana a na a kosztuje 1. Przy dopasowaniu skopiuj wartość po przekątnej.
Odczytywanie lewego sąsiada z prev zamiast z cur. Lewy sąsiad należy do bieżącego wiersza: oznacza wstawienie word2[j-1], gdy word1[:i] zostało już zamienione na word2[:j-1].
Porównywanie pozycji jedna po drugiej. Zliczanie miejsc, w których słowa się różnią, pomija wstawienia i usunięcia: dla garden i ardent daje 6, podczas gdy odpowiedź wynosi 2.
Zapamiętywanie wyników rekurencji dla słów o długości 500 liter. Głębokość wywołań osiąga 1000, czyli domyślny limit Pythona.

Najczęstsze pytania4

Jaka jest złożoność czasowa odległości edycyjnej?

Rozwiązanie z tabelą działa w czasie O(n × m), gdzie n i m to długości dwóch ciągów, ponieważ wypełnia jedną komórkę dla każdej pary prefiksów, wykonując stałą liczbę operacji. Pełna tabela wymaga O(n × m) pamięci, a tabela złożona z dwóch wierszy — O(min(n, m)). Zwykła rekurencja bez tabeli ma złożoność wykładniczą.

Czy odległość edycyjna jest tym samym co odległość Levenshteina?

Tak, ta wersja to odległość Levenshteina: wstawienie, usunięcie i zastąpienie kosztują po jednym. Odległość edycyjna to nazwa całej rodziny. Inne jej warianty dopuszczają mniej lub więcej edycji: tylko wstawienia i usunięcia dają n + m - 2 × LCS, tylko zastąpienia przy równych długościach dają odległość Hamminga, a dodanie zamiany dwóch sąsiednich liter daje wariant Damerau.

Jak uzyskać listę zmian, a nie tylko ich liczbę?

Zachowaj całą tablicę i cofaj się od dp[n][m]. Jeśli litery są takie same, przejdź po przekątnej bez edycji. W przeciwnym razie przejdź do sąsiedniej komórki o wartości mniejszej o jeden: ruch po przekątnej oznacza zastąpienie, w górę — usunięcie, w lewo — wstawienie. Zatrzymaj się przy dp[0][0] i odczytaj edycje w odwrotnej kolejności. Wersja z dwoma wierszami nie może tego zrobić samodzielnie, ponieważ odrzuciła wcześniejsze wiersze.

Czy odległość edycyjna może być obliczona za pomocą jednej tablicy?

Tak. Wypełnij jedną tablicę row w miejscu, od lewej do prawej. Zanim nadpiszesz row[j], nadal zawiera ono wartość z poprzedniego wiersza, a row[j-1] zawiera już wartość z bieżącego wiersza. Jedyną wartością, którą tracisz, jest wartość po przekątnej, więc zachowaj ją w zmiennej: zapisz starą wartość row[j] przed zapisaniem nowej i użyj jej jako wartości po przekątnej dla j + 1.

Python

def minDistance(word1, word2):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

word1 = "spot"
word2 = "stop"

Oczekiwane

Edit Distance

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Wypróbuj wszystkie trzy edycje z rekurencją

Uzupełnij tabelę przedrostków

Zachowaj tylko dwa wiersze

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania