Редактировать расстояние с различными словарями

Question

Мой вопрос похож на Algorithm to transform one word to another through valid words

Но есть большая разница. У меня есть одно фиксированное слово «JAMES» и различные словари как i/p. Конечно, я не могу препроцитировать словарь сейчас.

Поэтому мне нужно найти минимальную стоимость обработки «JAMES» до «JOHNY» с различными словарями в качестве входных данных.

В любом случае я мог бы предварительно обработать слово «JAMES», чтобы мне нужно выполнить минимальное количество вычислений расстояния редактирования во время выполнения? Что вы предлагаете?

Answer 1

Во-первых, вам нужно правильно определить свои правила - это «редактирование», позволяющее добавлять или удалять несколько символов, заменять один символ и т. Д.?

В любом случае - я бы начал с очевидного - создайте график, в котором каждое слово будет ссылаться на все те, к которым он может быть непосредственно отредактирован. Затем используйте рекурсию с ограничением глубины, отметив, что посещаемые элементы были «грязными», чтобы избежать циклов, а затем посмотрите, есть ли одноредактированное решение, двухрежимное решение и т. Д., Пока не найдете решение, или все пути грязны на этой глубине. (Если вы записываете глубину, пытающуюся в «грязном» члене, вам не нужно беспокоиться о том, чтобы очищать их каждый раз, когда вы увеличиваете ограничение глубины. Вы также можете отметить все грязные поддеревья, чтобы избежать повторного повторения в них .)

Answer 2

Я предполагаю, что правила аналогичны указанному вами вопросу, т. Е. Разрешено только одно редактирование, и каждое промежуточное слово должно присутствовать в данном словаре.

1. Создайте отдельные редактируемые версии исходной строки в строку назначения. для например: JOMES JAHES JAMNS Jamey

RECURSE для каждого из этих слов и продолжать создавать узлы для каждого уникального слова. Просто создайте ребра, если узел уже создан. Это завершает предварительную обработку.

Теперь, используя словарь, найдите все слова первого уровня в словаре. Для всех матчей найдите все слова второго уровня и т. Д., Пока не дойдете до целевого слова.