Word Jumble Algorithm
Учитывая беспорядок слова (т.е. ofbaor), каков был бы подход для восстанавливания букв для создания реального слова (т.е. foobar)? Я видел, что это имело несколько подходов, и я думаю, что знаю, как я сделал бы это в.NET, но я любопытный видеть то, на что похожи некоторые другие решения (всегда счастливый видеть, оптимально ли мое решение или не).
Это не домашняя работа или что-либо как этот, я просто видел, что слово смешалось в локальном разделе статьи комиксов (да, старая добрая сформированная газетная бумага), и инженер во мне начал думать.
править: отправьте некоторый псевдо код или реальный код, если Вы можете; всегда хорошо попытаться развернуть знание языка путем наблюдения примеров как это.
5 ответов
Имейте словарь, который вводится буквами каждого слова в отсортированном порядке. Затем попробуйте перемешать и отсортировать буквы - найдите все слова в словаре по этой строке отсортированных букв.
Так, например, слова «медведь» и «голый» будут в словаре следующим образом:
key word
----- ------
aber bear
aber bare
И если вам дадут путаницу, «ухо», вы отсортируете буквы на « aber 'и сможет найти оба возможных слова в словаре.
В CodeProject есть пара статей здесь и здесь . Второй использует рекурсию. Википедия также описывает пару алгоритмов здесь . В статье в Википедии также упоминается программа под названием Jumbo, которая использует более эвристический подход, который решает проблему, как это сделал бы человек. Кажется, есть несколько подходов к проблеме.
В зависимости от длины строки подход WhirlWind может быть быстрее, но альтернативный способ сделать это, имеющий более или менее O (n) сложность, заключается в том, что вместо создания всех перестановок строки и их поиска вы идете просмотреть все слова в словаре и посмотреть, можно ли каждое из них построить из входной строки.
действительно умный алгоритм, который заранее знает количество слов в словаре, мог бы сделать что-то вроде этого:
sort letters in jumbled string
if factorial(length of jumbled string) > count of words in dictionary:
for each word in dictionary:
sort letters in dictionary word
if sorted letters in dictionary word == sorted letters in jumbled string:
append original dictionary word to acceptable word list
else:
create permutation list of jumbled letters
for each permutation of letters:
search in dictionary for permutation
if permutation in dictionary:
add word to acceptable word list
Создайте все перестановки строки и найдите их в словаре.
Вы можете оптимизировать, просматривая более короткие строки, начинающиеся с слов, и, если в словаре нет слов подходящей длины, которые начинаются с этих строк, исключая перестановки, начинающиеся с этих букв, из дальнейшего рассмотрения.