Решение задачи #33. Python Яндекс CodeRun, Расстояние по Левенштейну

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Расстояние по Левенштейну.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Дана текстовая строка. С ней можно выполнять следующие операции:

Заменить один символ строки на другой символ.
Удалить один произвольный символ.
Вставить произвольный символ в произвольное место строки.

Например, при помощи первой операции из строки «СОК» можно получить строку «СУК», при помощи второй операци — строку «ОК», при помощи третьей операции — строку «СТОК».

Минимальное количество таких операций, при помощи которых можно из одной строки получить другую, называется стоимостью редактирования или расстоянием Левенштейна.

Определите расстояние Левенштейна для двух данных строк.

Формат ввода:
Программа получает на вход две строки, длина каждой из которых не превосходит 1000 символов, строки состоят только из заглавных латинских букв.

Формат вывода:
Требуется вывести одно число — расстояние Левенштейна для данных строк.

Решение:

Python

import sys

def levenshtein_distance(str1, str2):
    """
    Вычисляет расстояние Левенштейна между двумя строками.

    Args:
        str1: Первая строка.
        str2: Вторая строка.

    Returns:
        Расстояние Левенштейна между строками.
    """

    n = len(str1)
    m = len(str2)

    # Создаем матрицу (n+1) x (m+1) для хранения расстояний
    # dp[i][j] - расстояние между str1[:i] и str2[:j]
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # Инициализация первого столбца и первой строки
    # dp[i][0] = i - количество удалений, чтобы получить пустую строку из str1[:i]
    # dp[0][j] = j - количество вставок, чтобы получить str2[:j] из пустой строки
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j

    # Заполняем оставшуюся часть матрицы
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cost = 0 if str1[i - 1] == str2[j - 1] else 1  # Стоимость замены
            dp[i][j] = min(
                dp[i - 1][j] + 1,      # Удаление из str1
                dp[i][j - 1] + 1,      # Вставка в str1
                dp[i - 1][j - 1] + cost # Замена/совпадение
            )
    return dp[n][m]

def main():
    """
    Основная функция программы.
    Считывает входные данные и выводит результат.
    """
    str1 = sys.stdin.readline().strip()
    str2 = sys.stdin.readline().strip()

    result = levenshtein_distance(str1, str2)
    print(result)

if __name__ == "__main__":
    main()

Объяснение кода

Алгоритм, используемый в коде, основан на динамическом программировании. Он строит матрицу dp, где dp[i][j] представляет собой расстояние Левенштейна между первыми i символами строки str1 и первыми j символами строки str2.

Инициализация:
Первая строка и первый столбец матрицы инициализируются значениями от 0 до n и от 0 до m соответственно. Это соответствует случаям, когда одна из строк пустая.

Заполнение матрицы:
Для каждой ячейки dp[i][j] вычисляется минимальное значение из трех вариантов:
dp[i-1][j] + 1: Удаление символа из str1.
dp[i][j-1] + 1: Вставка символа в str1.
dp[i-1][j-1] + cost: Замена символа в str1 (если символы не совпадают, cost = 1, иначе cost = 0).

Результат:
Значение dp[n][m] содержит искомое расстояние Левенштейна.

Данный код достаточно оптимизирован для решения задачи с ограничениями по длине строк в 1000 символов. Использование динамического программирования позволяет избежать рекурсивных вызовов и экспоненциального роста времени выполнения. Временная сложность алгоритма O(n*m), где n и m - длины строк. Использование матрицы dp для хранения промежуточных результатов предотвращает повторные вычисления. Код эффективно решает задачу и проходит тесты с заданными ограничениями по времени и памяти.

Источник решения: hdhai.com