Преобразование одной строки в другую

Question

Это вопрос интервью. Мне нужно преобразовать строку a в b, чтобы только один алфавит был изменен за раз, и после каждого изменения преобразованная строка находится в словаре. Вам нужно сделать это в минимальном количестве преобразований. Например, переход от кошки -> мальчик может быть сделан следующим образом:

cat-->bat-->bot-->boy (if dictionary has bat and bot) 

Я могу думать о создании дерева префиксов (TRIE), на этот вопрос, но я не уверен, как действовать, как только у меня есть Trie. Может ли кто-нибудь предложить возможный подход? Я стараюсь избегать использования подхода грубой силы.

Answer 1

Вы уже нарушили проблему в префиксном trie.

Есть еще несколько шагов, чтобы предпринять, чтобы прийти к решению:

1. Написать функцию, которая принимает входную строку и ищет возможные преобразования, запрашивая TRIE-словарь.
2. Придумайте an admissible heuristic, который вы можете использовать для выбора результатов.
3. Используйте известный алгоритм кратчайшего пути, например the A* search algorithm.

Answer 2

Если вы хотите узнать, как рассчитывать минимальное количество одиночных изменений, просмотрите Levenshtein distance. Однако это предполагает, что допускаются только вставка, удаление и замена.

Для вашего примера, изменение cat -> boy имеет левенштейновское расстояние 3, с тремя подстановками (c-> b, a-> o, t-> y).

Если транспонирование также разрешено, тогда вы должны рассмотреть Damerau–Levenshtein distance.

Например, cat -> cta имеет Levenshtein расстояние от 2, и Damerau-Levenshtein расстояние от 1