1.py

# 69475225

# Для того чтобы посчитать минимальное кол-во необходимых правок, нужно знать
# всего лишь предыдущие значения и текущие(два ряда матрицы), а не все как при
# НОП или при похожем решение, когда мы используем двумерный массив, но
# алгоритм получения необходимого ответа похожий, для этого используется
# формула(переход динамики):  min(result[j - 1], prev[j], prev[j - 1]) + 1, а
# ответ будет находится в конце массива.
# В самом начале массива prev находится крайний случай, т.е если сравнивать
# пустую строку с i-ым количеством символов.
# В самом начале алгоритма, в массиве result, также определён крайний случай,
# в нём изначально находится максимальное кол-во правок для j-ого кол-ва
# символов, т.к. сравнение идёт так же с пустой строкой.
# Временная сложность: O(N*M) N/M - длины строк
# Пространственная сложность: O(min(n,m)) N/M - длины строк

from typing import List


def get_levenshtein_distance(s1: str, s2: str) -> int:
    if s2 > s1:
        s2, s1 = s1, s2
    m, n = len(s1), len(s2)
    result: List[int] = list(range(n + 1))
    prev: List[int] = [0] * (n + 1)
    for i in range(1, m + 1):
        # Помогает избежать лишнего выделения памяти
        for k in range(len(prev)):
            prev[k] = 0
        prev[0] = i
        prev, result = result, prev
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                result[j] = prev[j - 1]
            else:
                result[j] = min(result[j - 1], prev[j], prev[j - 1]) + 1
    return result[n]


def main() -> None:
    print(get_levenshtein_distance(input(), input()))


if __name__ == "__main__":
    main()