Edit Distance

Q: Можно ли решить задачу о редакционном расстоянии с помощью одного массива?

Да. Заполняйте один массив row на месте, слева направо. Прежде чем перезаписать row[j] , в нём всё ещё хранится значение из строки выше, а в row[j-1] уже хранится значение текущей строки. Теряется только диагональное значение, поэтому сохраните старое значение row[j] в переменную и используйте его как диагональное значение для j + 1 .

СложноДинамическое программирование

+10

Тебе даны два слова: word1 и word2. Одно изменение преобразует word1 одним из трёх способов: вставить букву в любое место, удалить букву или заменить букву на другую. Верни минимальное количество изменений, необходимое, чтобы превратить word1 в word2.

Функция

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

word1string: слово, которое вы редактируете
word2string: слово «достичь»
Возвращаетinteger: минимальное число вставок, удалений и замен, необходимых, чтобы превратить word1 в word2

Ограничения

1 ≤ word1.length ≤ 500
1 ≤ word2.length ≤ 500
Оба слова содержат только строчные английские буквы.

Примеры

Ввод: word1 = "spot"word2 = "stop"
Вывод: 2
Пояснение: Замените p на t, а t на p: spot становится stot, затем stop. Одного изменения недостаточно, потому что слова различаются в двух местах, а вставка или удаление изменили бы длину.

Ввод: word1 = "garden"word2 = "ardent"
Вывод: 2
Пояснение: Удалите g, чтобы получить arden, затем вставьте t в конец, чтобы получить ardent. Замена буквы за буквой обошлась бы в 6, потому что эти два слова различаются в каждой позиции.

Ввод: word1 = "rain"word2 = "shine"
Вывод: 3
Пояснение: Замени r на s и a на h, затем вставь e. Две правки не сработают: r и a отсутствуют в shine, поэтому для каждой нужна правка, сохраняющая длину, а слово всё ещё должно увеличиться на один символ.

Дополнительный вопрос

Можешь также вернуть один кратчайший список изменений, помимо их количества?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Редактирования взаимодействуют: garden и ardent различаются во всех шести позициях, но достаточно двух редактирований. Поэтому посмотри на последнюю букву каждого слова. Либо они совпадают, либо одно из трёх редактирований приводит к совпадению, и каждый выбор оставляет ту же задачу для более коротких префиксов. Таблица решает каждую пару префиксов один раз.

Попробуй все три изменения с рекурсией

Верно, но не успевает на самых больших тестах

Идея

Пусть edits(i, j) — минимальное количество правок, необходимое, чтобы превратить суффикс word1[i:] в word2[j:]. Если первые буквы совпадают, оставь их и передвинь оба индекса: тратить правку на совпадающую букву никогда не выгодно. Иначе возьми 1 плюс наименьшее значение из трёх вызовов: замена передвигает оба индекса, удаление word1[i] передвигает i, а вставка word2[j] передвигает j. Когда в одном слове заканчиваются буквы, каждая оставшаяся буква в другом требует одной правки.

При каждом несовпадении выполняются три вызова: для двух слов длиной 15 букв, в которых нет общих букв, потребуется около 6.7 × 10^10 вызовов. Однако существует всего (n+1) × (m+1) разных пар (i, j), поэтому почти каждый вызов повторяет один из предыдущих.

Алгоритм

Если i выходит за конец word1, верни m - j; если j выходит за конец word2, верни n - i.
Если word1[i] == word2[j], верни edits(i+1, j+1).
Иначе верни 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)).
Ответ — 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)

Заполните таблицу префиксов

Идея

Пусть dp[i][j] — минимальное количество правок, необходимых, чтобы превратить первые i букв word1 в первые j букв word2. Если word1[i-1] равно word2[j-1], скопируй значение по диагонали dp[i-1][j-1]. В противном случае прибавь 1 к наименьшему из соседних значений: диагональное соответствует замене, ячейка сверху — удалению word1[i-1], ячейка слева — вставке word2[j-1]. Базовые строки и столбцы не заполнены нулями: чтобы превратить i букв в пустую строку, нужно выполнить i удалений, поэтому dp[i][0] = i, и аналогично dp[0][j] = j.

Для преобразования spot в stop последняя строка имеет вид [4, 3, 2, 2, 2]. В последней ячейке сравниваются t и p; диагональное значение (преобразование spo в sto) равно 1, а значения в двух других соседних ячейках равны 2, поэтому ответ равен 1 + 1 = 2. Два слова длиной 500 букв заполняют 2.5 × 10^5 ячеек, каждую за постоянное время.

Алгоритм

Создай dp с (n+1) × (m+1) ячейками, dp[i][0] = i и dp[0][j] = j.
Для i от 1 до n и j от 1 до m: если word1[i-1] == word2[j-1], установи dp[i][j] = dp[i-1][j-1].
В противном случае установи dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
Верни 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]

Оставьте только две строки

Идея

Строка i читает только строку i-1 и собственные ячейки слева, поэтому достаточно двух массивов: prev для завершённой строки и cur для заполняемой строки. Диагональ — это prev[j-1], сверху — prev[j], а слева — cur[j-1]. Теперь базовый столбец находится в первой ячейке каждой строки, поэтому задайте cur[0] = i перед заполнением строки i.

Преобразование word2 в word1 требует столько же операций редактирования, поскольку вставки и удаления меняются местами. Поменяйте слова местами, чтобы строки шли вдоль более короткого слова: min(n, m) + 1 чисел в каждой строке вместо таблицы размером до 251,001 ячейки, при тех же трудозатратах O(n × m).

Алгоритм

Если word2 длиннее, чем word1, поменяй их местами.
Задай prev = [0, 1, ..., m].
Для каждого i от 1 до n задай cur[0] = i и заполни cur[1..m] по правилу таблицы, считывая диагональное значение и значение сверху из prev, а значение слева — из cur. Затем поменяй prev и cur местами.
Верни 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]

Ловушки и крайние случаи

Заполнение строки 0 и столбца 0 нулями, как в задаче о наибольшей общей подпоследовательности. Преобразование abc в пустой префикс требует 3 удалений, а не 0.
Забыть про cur[0] = i в версии с двумя строками. В первой ячейке сохраняется значение из строки на две строки выше, и все ячейки после неё неверны.
Оплачивать редактирование при совпадении. Если для одинаковых букв использовать 1 + min(...), преобразование a в a будет стоить 1.
Считывать соседа слева из prev вместо cur. Слева находится вставка word2[j-1] в текущей строке.
Мемоизированная рекурсия в Python для слов длиной 500 букв. Глубина вызовов достигает 1000, что превышает предел рекурсии по умолчанию.

Частые вопросы3

Какова временная сложность расстояния редактирования?

Решение с таблицей заполняет одну ячейку для каждой пары префиксов за постоянное время: временная сложность O(n × m) для строк длины n и m. Для полной таблицы требуется O(n × m) памяти, а при использовании двух строк — O(min(n, m)). Простая рекурсия без таблицы имеет экспоненциальную сложность.

Является ли расстояние редактирования тем же, что и расстояние Левенштейна?

Эта версия — расстояние Левенштейна: вставка, удаление и замена стоят по одной единице. Расстояние редактирования — это общее название. Только вставки и удаления дают n + m - 2 × LCS, только замены при равной длине дают расстояние Хэмминга, а добавление перестановки двух соседних букв даёт версию Дамерау.

Можно ли решить задачу о редакционном расстоянии с помощью одного массива?

Да. Заполняйте один массив row на месте, слева направо. Прежде чем перезаписать row[j], в нём всё ещё хранится значение из строки выше, а в row[j-1] уже хранится значение текущей строки. Теряется только диагональное значение, поэтому сохраните старое значение row[j] в переменную и используйте его как диагональное значение для j + 1.

def minDistance(word1, word2):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

word1 = "spot"
word2 = "stop"

Ожидаемый вывод

Edit Distance

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуй все три изменения с рекурсией

Заполните таблицу префиксов

Оставьте только две строки

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи