Строка преобразования

Question

Я наткнулся на следующую статью , которая заинтересовала меня именно этой проблемой.

Учитывая два слова "CAT", "FAR" определяет, можно ли получить с первого ко второму с помощью единичных преобразований действительных слов .... например. 1 преобразование переводит вас из CAT в CAR, меняя T на R, а затем еще переводит вас из CAR в FAR, меняя C на F ... все действительны английский слова.

Есть идеи? Не совсем уверен, как начать быть честным. Если вы укажете мне правильное направление, этого будет достаточно. Спасибо!

Answer 1

Как отмечено в этом ответе (спасибо, aix), это проблема кратчайшего пути, и ее можно эффективно решить с помощью алгоритма A * с использованием Хэмминга расстояние (т. е. количество букв, на которое различаются два слова) как эвристика.

Answer 2

Есть 3 пункта, которые следует учитывать:

1 Сколько символов отличаются между двумя заданными словами?Это просто не символ, но его позиция в слове также имеет значение.Так что сравним по положению.

2 Определите для каждого преобразования, является ли полученное слово допустимым английским словом.Здесь потребуется некоторая ссылка на правильные слова.

3 Определите последовательность преобразований для каждого промежуточного слова.

Думаю, это будет попытка ошибочного подхода.Любой алгоритм возврата будет хорошим выбором.