You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, replace a character. Now given two words — word1 and word2 — find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)
У кого нибудь есть идеи элегантного решения?
Касательно второго интересную статью привел Віктор Гайдін, но решения целевой задачи из нее к сожалению не следует...
По-моєму це Levenshtein distance. Правда я не зрозумів, до чого переше речення завдання...
Не знаю насколько это элегантное решение. На php строк 100.
P.S. 2Модератор: Якщо можливо, видаліть, будь ласка мій
У кінці для word1 будуємо ’r< =2’-коло як об’єднання ’r=1’-кіл елементів, які належать до його ’r=1’-кола, тоді ’r< =3’-коло як об’єднання ’r=1’-кіл
викидання із нього якої-небудь букви належить словнику; якщо так, додаємо більше слово ’r=1’-кола меншого, а менше — до ’r=1’-кола більшого. І таке в циклі по всіх словах словника. На другому кроці будуємо допоміжний псевдословник, який складатиметься із всеможливих результатів викидання із слів словника 1 букви; при цьому кожен елемент псевдословника повинен містити посилання на слова, від яких він утворений (останніх може бути декілька);
Приклад одного з алгоритмів. Спочатку із кожним словом із словника асоціюємо множину інших слів, які можна отримати із нього за одну операцію. Для цього на першому кроці беремо слово із словника і перевіряємо, чи результат
класика динамічного програмування, наприклад: algolist.manual.ru/search/lcs
Наверно, имелось в виду, что полученое в результате каждой операции слово должно принадлежать словарю.
Поудалять все несовпадающие символы, а потом доставить недостающие?:)
crypto5
anonymous
Victor Haydin
Ivan M
11 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів