Проблемы Python: вычислить расстояние редактирования между двумя заданными строками

Проблемы Python — 1: Упражнение-52 с решением

Из Википедии, бесплатной энциклопедии
В компьютерной лингвистике и информатике расстояние редактирования — это способ количественной оценки того, как две разные строки (например, слова) относятся друг к другу путем подсчета минимального количества операций, необходимых для преобразования одной строки в другую. Расстояние редактирования позволяет найти приложения в обработке естественного языка, где автоматическая коррекция орфографии может определять возможные варианты исправления слова с ошибкой путем выбора слов из словаря, которые находятся на небольшом расстоянии от рассматриваемого слова. В биоинформатике его можно использовать для количественной оценки сходства последовательностей ДНК, которые можно рассматривать как строки из букв A, C, G и T.
Эту проблему задала компания Google.
Расстояние редактирования между двумя строками относится к минимальному количеству вставок, удалений и замен символов, необходимых для замены одной строки на другую. Например, расстояние редактирования между «котенком» и «сидящим» равно трем: замените «k» на «s», замените «e» на «i» и добавьте «g».
Напишите программа Python для вычисления расстояния редактирования между двумя заданными строками.

Пример решения :

Код Python :

  def edit_distance (string1, string2): "" "Ссылка: https://bit.ly/2Pf4a6Z" "" if len (string1)>  len (строка2): разница = len (строка1) - len (строка2) строка1 [: разница] elif len (строка2)> len (строка1): разница = len (строка2) - len (строка1) строка2 [: разница] иначе:  разница = 0 для i в диапазоне (len (строка1)): если строка1 [i]! = строка2 [i]: разница + = 1 вернуть разницу печать (edit_distance ("котенок", "сидит")) # 3print (edit_distance ("  medium "," median ")) # 2  

Пример вывода:

 32 

Блок-схема:

Редактор кода Python:

Оцените статью
nanomode.ru
Добавить комментарий