Рассмотрим задачу "Идентичные строки" из 5-ого модуля.
Для решения данной задачи воспользуемся двумерной матрицей, чтобы найти расстояние Левенштейна.
Расстояние Левенштейна, или редакционное расстояние — метрика cходства между двумя строковыми последовательностями.
Расстоянием метрика названа условно. Алгоритм помогает найти минимальное количество преобразований, чтобы превратить одну строку в другую, в частности те, в которых нужно убрать символ. Например, понадобится всего 2 шага, чтобы уравнять строки sea и eat (убирая t и s).
Первым делом создадим нулевую матрицу dp размером n * m, где n, m - длины исходных слов s1 и s2.