Привет всем, такая задача.
Есть текст с неправильными словами, которые надо исправить согласно словам в словаре.
Причём:
- для изменения слова допускается только 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" действий (именно удалений-вставок, а не замен) будет больше.
Может кто сталкивался уже?