Расстояние редактирования шаг за шагом
Вставляйте, удаляйте и заменяйте символы для преобразования
«Расстояние редактирования шаг за шагом» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Что измеряет расстояние редактирования
Расстояние редактирования — это минимальное количество изменений отдельных символов, необходимых, чтобы превратить одну строку в другую. Оно показывает, насколько на самом деле различаются два слова.
Три операции
В рамках одного изменения можно вставить, удалить или заменить один символ. В стандартной задаче каждая операция стоит ровно единицу.
Определите состояние
Пусть dp[i][j] — количество изменений, необходимых, чтобы превратить первые i символов A в первые j символов B.
Совпадение бесплатно
Если текущие символы уже совпадают, изменение не требуется. Просто перенесите значение по диагонали без изменений.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]Иначе заплатите единицу
Если символы различаются, возьмите значение из самого дешёвого соседнего варианта и прибавьте одно изменение. Этот шаг минимум плюс один учитывает все три операции.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Какой сосед что означает
Ячейка сверху означает удаление, ячейка слева — вставку, а диагональная ячейка — замену. Минимум просто выбирает самый дешёвый вариант.
Базовые случаи для пустой строки
Чтобы превратить строку длины i в пустую строку, нужно выполнить i удалений. Поэтому заполните первую строку и столбец значениями 0, 1, 2 и так далее.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jЗадайте размер таблицы
Используйте сетку размера n+1 на m+1, чтобы у пустых префиксов были собственные строка и столбец. Такое дополнение упрощает циклы.
dp = [[0] * (m+1) for _ in range(n+1)]Заполняйте по порядку
Перебирайте i и j от 1 по возрастанию. Каждая ячейка зависит только от уже заполненных соседей сверху, слева и по диагонали.
for i in range(1, n+1):
for j in range(1, m+1):
...Прочитайте расстояние
Минимальное количество изменений оказывается в углу. Ваш ответ — это dp[n][m] после полного заполнения таблицы.
distance = dp[n][m]Стоимость и варианты
Временная сложность этого алгоритма — O(n умножить на m). В реальных задачах у операций могут быть разные стоимости, но та же рекуррентная формула всё равно работает.
Быстрая проверка
Символы A[i-1] и B[j-1] различаются. Какая рекуррентная формула задаёт расстояние редактирования?
Повторение: расстояние редактирования
При совпадении перенесите значение по диагонали, а при несовпадении возьмите единицу плюс минимум из трёх соседних значений. Инициализируйте границы и прочитайте dp[n][m]. ✏️
Часто задаваемые вопросы
Урок «Расстояние редактирования шаг за шагом» бесплатный?
Да — полный текст урока «Расстояние редактирования шаг за шагом» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Расстояние редактирования шаг за шагом»?
Вставляйте, удаляйте и заменяйте символы для преобразования Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Расстояние редактирования шаг за шагом»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Подсчёт путей по сетке
- Минимальная сумма пути с препятствиями
- Наибольшая общая подпоследовательность
- Расстояние редактирования шаг за шагом