Это вопрос интервью:
Дана строка, найти все ее перестановки, которые являются словом в словаре.
Мое решение:
Поместите все слова словаря в дерево суффиксов, а затем выполните поиск каждой перестановки строки в дереве.
Время поиска равно O(n), где n — размер строки. Но строка может иметь n! перестановок.
Как повысить эффективность?
Ваш общий подход неплох.
Однако вы можете предотвратить поиск каждой перестановки, переставив свое слово так, чтобы все его символы были в алфавитном порядке, а затем выполните поиск в словаре, где каждое слово аналогичным образом перестроено в алфавитном порядке и сопоставлено с исходным словом.
Я понимаю, что это может быть немного сложно понять как есть, поэтому вот пример. Скажите, что ваше слово прыжок. Измените его на aelp.
Теперь в вашем словаре могут быть слова мольба и бледность. Сделав так, как было предложено, ваш словарь будет (среди прочего) содержать следующие сопоставления:
...
aelp -> pale
aelp -> plea
...
Так что теперь, чтобы найти ваши анаграммы, вам нужно найти записи только для aelp (используя, например, предложенный подход с суффиксным деревом), а не для всех 4! = 24 варианта скачка.
Быстрое альтернативное решение - все зависит от размеров рассматриваемых структур данных.
Если словарь разумно мал, а строка достаточно длинна, вы можете просмотреть каждую запись в словаре и выяснить, являются ли они перестановкой строки. Вы можете быть умнее - вы можете сортировать словарь и пропускать определенные записи.
Вы можете построить карту из отсортированного списка символов в список слов.
Например, учитывая эти:
Array (him, hip, his, hit, hob, hoc, hod, hoe, hog, hon, hop, hos, hot)
вы бы отсортировали их внутри:
Array (him, hip, his, hit, bho, cho, dho, eho, gho, hno, hop, hos, hot)
сортировать результат:
Array (bho, cho, dho, eho, gho, him, hip, his, hit, hno, hop, hos, hot)
В этом небольшом примере у нас нет совпадения, но для определенного слова вы должны отсортировать его внутри, и с этим ключом посмотреть на свою карту.
Почему бы вам не использовать хэш-карту для хранения слов словаря? Таким образом, вы получаете время поиска O (1). И если ваш ввод на английском языке, вы можете построить другую таблицу, чтобы указать все возможные буквы в вашем словаре, используя эту таблицу, вы можете отфильтровать некоторые входные данные в начале. Ниже приведен пример:
result_list = empty;
for(char in input)
{
if(char not in letter_table)
{
return result_list;
}
}
for(entry in permutations of input)
{
if(entry in dictionary_hash_table)
{
result_list->add_entry();
}
}
return result_list
Вы должны поместить слова в попытку. Затем вы можете искать слово по мере создания перестановок. Вы можете пропускать целые блоки перестановок, если первая часть отсутствует в дереве.
http://en.wikipedia.org/wiki/Trie
Другим простым решением может быть следующий алгоритм:
1) Используйте «next_permutation», чтобы найти уникальную перестановку.
2) Используйте "find/find_if", чтобы найти его по словарю.
