Привет всем!
Есть текст с неправильными словами, которые надо исправить согласно словам в словаре.
Причём:
— для изменения слова допускается только 2 операции: вставка и/или удаление символа;
— если это две вставки или два удаления, то эти два символа не должны находиться рядом;
Если под исправление подходит несколько слов из словаря, то отобразить их в тексте внутри фигурных скобок.

Пример.

Словарь:
rain the his main mainly plain

Текст:
hte mainy lain

В результате должно быть:
the {main mainly} plain

Сначала думал, что достаточно будет использовать алгоритм дистанции Левенштейна. Например, если сравнивать "hte" с "the", то он выдаст длину 2, для "his" тоже. И для самого алгоритма это правильно (т.к. работает заменами), но по заданию подойдёт только "the", т.к. два действия: сначала удаление в начале слова символа "h" и потом добавление "h" между "t" и "e".
"his" не подойдёт, т.к. для приведения слова "hte" к "his" действий (именно удалений-вставок, а не замен) будет больше.
Может кто сталкивался уже, в какую сторону будет правильно думать?