Edit Distance

Q: Czy odległość edycyjną można obliczyć za pomocą jednej tablicy?

Tak. Wypełniaj jedną tablicę row w miejscu, od lewej do prawej. Zanim nadpiszesz row[j] , nadal zawiera ona wartość z poprzedniego wiersza, a row[j-1] zawiera już wartość z bieżącego wiersza. Tracona jest tylko wartość na przekątnej, więc zapisz starą wartość row[j] w zmiennej i użyj jej jako wartości na 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: wstawienie litery w dowolnym miejscu, usunięcie litery lub zastąpienie litery inną. Zwróć najmniejszą liczbę edycji potrzebną do przekształcenia word1 w word2.

Funkcja

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

word1string: edytowane przez ciebie słowo
word2string: słowo osiągnąć
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ż 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ż oba słowa różnią się na każdej pozycji.

Wejście: word1 = "rain"word2 = "shine"
Wyjście: 3
Wyjaśnienie: Zamień r na s i a na h, a następnie wstaw e. Dwie edycje nie wystarczą: r i a nie występują w shine, więc każda z nich wymaga edycji, która zachowuje długość, a słowo nadal musi wydłużyć się o jeden znak.

Pytanie dodatkowe

Czy możesz również zwrócić jedną najkrótszą listę zmian, oprócz ich liczby?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Zmiany oddziałują na siebie: garden i ardent różnią się na wszystkich sześciu pozycjach, a jednak wystarczą dwie zmiany. Przyjrzyj się więc ostatniej literze każdego słowa. Albo obie litery są takie same, albo jedna z trzech zmian sprawia, że stają się takie same, a każdy wybór pozostawia ten sam problem dla krótszych prefiksów. Tablica rozwiązuje raz każdą parę prefiksów.

Wypróbuj wszystkie trzy zmiany z rekurencją

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

Intuicja

Niech edits(i, j) oznacza najmniejszą liczbę edycji potrzebnych do przekształcenia sufiksu word1[i:] w word2[j:]. Jeśli pierwsze litery są takie same, zachowaj je i przesuń oba indeksy: wykonanie edycji na pasującej literze nigdy nie pomaga. W przeciwnym razie dodaj 1 do najmniejszego wyniku spośród trzech wywołań: zamiana przesuwa oba indeksy, usunięcie word1[i] przesuwa i, a wstawienie word2[j] przesuwa j. Gdy w jednym słowie zabraknie liter, każda pozostała litera w drugim wymaga jednej edycji.

Każda niezgodność rozpoczyna trzy wywołania: dla dwóch 15-literowych słów, które nie mają żadnej wspólnej litery, potrzeba około 6.7 × 10^10 wywołań. Istnieje jednak tylko (n+1) × (m+1) różnych par (i, j), więc niemal każde wywołanie powtarza wcześniejsze.

Algorytm

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)).
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

Niech dp[i][j] oznacza najmniejszą liczbę edycji potrzebnych do przekształcenia pierwszych i liter słowa word1 w pierwsze j liter słowa word2. Jeśli word1[i-1] jest równe word2[j-1], przepisujemy wartość z przekątnej dp[i-1][j-1]. W przeciwnym razie dodajemy 1 do kosztu najtańszego sąsiada: przekątna oznacza zamianę, komórka powyżej — usunięcie word1[i-1], a komórka po lewej — wstawienie word2[j-1]. Wiersz i kolumna bazowa nie zawierają zer: przekształcenie i liter w pusty ciąg wymaga i usunięć, więc dp[i][0] = i, i analogicznie dp[0][j] = j.

Dla przekształcenia spot w stop ostatni wiersz to [4, 3, 2, 2, 2]. W końcowej komórce porównujemy t z p; wartość na przekątnej (przekształcenie spo w sto) wynosi 1, a wartości pozostałych sąsiadów wynoszą 2, więc wynik to 1 + 1 = 2. Dwa słowa o długości 500 wypełniają 2.5 × 10^5 komórek, z których każda jest obliczana w stałym czasie.

Algorytm

Utwórz dp z (n+1) × (m+1) komórkami, dp[i][0] = i i dp[0][j] = 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, więc wystarczą dwie tablice: prev dla ukończonego wiersza i cur dla wiersza, który wypełniasz. Przekątna to prev[j-1], komórka powyżej to prev[j], a po lewej to cur[j-1]. Kolumna bazowa znajduje się teraz w pierwszym elemencie każdego wiersza, więc przed wypełnieniem wiersza i ustaw cur[0] = i.

Przekształcenie word2 w word1 wymaga tyle samo edycji, ponieważ wstawienia i usunięcia zamieniają się rolami. Zamień słowa miejscami, aby wiersze przebiegały wzdłuż krótszego z nich: min(n, m) + 1 liczb w wierszu zamiast tabeli o rozmiarze do 251,001 komórek, przy takim samym nakładzie pracy O(n × m).

Algorytm

Jeśli word2 jest dłuższe niż word1, zamień je miejscami.
Ustaw prev = [0, 1, ..., m].
Dla każdego i od 1 do n ustaw cur[0] = i i wypełnij cur[1..m] zgodnie z regułą tabeli, odczytując wartości po przekątnej i powyżej z prev, a z lewej z cur. Następnie 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

Wypełnianie zerami wiersza 0 i kolumny 0, jak w przypadku najdłuższego wspólnego podciągu. Przekształcenie abc w pusty prefiks kosztuje 3 usunięcia, a nie 0.
Pomijanie cur[0] = i w wersji z dwoma wierszami. Pierwszy element zachowuje wartość sprzed dwóch wierszy, a każda kolejna komórka ma nieprawidłową wartość.
Wykonywanie edycji przy dopasowaniu. Przy użyciu 1 + min(...) dla identycznych liter przekształcenie a w a kosztuje 1.
Odczytywanie sąsiada po lewej z prev zamiast z cur. Lewy sąsiad odpowiada wstawieniu word2[j-1] w bieżącym wierszu.
Zapamiętywana rekurencja w Pythonie dla słów o długości 500 liter. Wywołania sięgają głębokości 1000, przekraczając domyślny limit rekurencji.

Najczęstsze pytania3

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

Rozwiązanie z tabelą wypełnia jedną komórkę dla każdej pary prefiksów w stałym czasie: czas O(n × m) dla długości n i m. Wykorzystuje O(n × m) pamięci dla pełnej tabeli lub O(min(n, m)) przy użyciu dwóch wierszy. Zwykła rekurencja bez tabeli ma złożoność wykładniczą.

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

Ta wersja to odległość Levenshteina: wstawienie, usunięcie i zastąpienie kosztują po jednym. Odległość edycyjna to nazwa rodziny. Same wstawienia i usunięcia dają n + m - 2 × LCS, same zastąpienia przy równych długościach dają odległość Hamminga, a dodanie zamiany dwóch sąsiadujących liter daje wersję Damerau.

Czy odległość edycyjną można obliczyć za pomocą jednej tablicy?

Tak. Wypełniaj jedną tablicę row w miejscu, od lewej do prawej. Zanim nadpiszesz row[j], nadal zawiera ona wartość z poprzedniego wiersza, a row[j-1] zawiera już wartość z bieżącego wiersza. Tracona jest tylko wartość na przekątnej, więc zapisz starą wartość row[j] w zmiennej i użyj jej jako wartości na przekątnej dla j + 1.

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

Test #1

Test #2

Test #3

Argumenty

word1 = "spot"
word2 = "stop"

Oczekiwany wynik

Edit Distance

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Wypróbuj wszystkie trzy zmiany z rekurencją

Uzupełnij tabelę przedrostków

Zachowaj tylko dwa wiersze

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania