По заданной строке найдите все ее перестановки, являющиеся словом в словаре.

Question

Это вопрос интервью:

По заданной строке найдите все ее перестановки, являющиеся словом в словаре.

Мое решение:

Поместите все слова словаря в дерево суффиксов, а затем ищите каждую перестановку строки в дереве.

Время поиска: O(n), где n - размер строки. Но строка может иметь n! перестановок.

Как мне повысить эффективность?

Answer 1

Ваш общий подход неплох.

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

Я понимаю, что это может быть немного трудно понять, как есть, так что вот пример.Скажи, что твое слово скачок .Переставьте это в aelp .

Теперь в вашем словаре могут быть слова plea и pale .Сделав, как предложено, ваш словарь будет (среди прочего) содержать следующие сопоставления:

...
aelp -> pale
aelp -> plea
...

Итак, теперь, чтобы найти ваши анаграммы, вам нужно только найти записи для aelp (используянапример, подход суффиксного дерева как предложено), а не для всех 4!= 24 перестановки прыжок .

Answer 2

Быстрое альтернативное решение - все зависит от размеров рассматриваемых структур данных.

Если словарь достаточно мал, а строка достаточно длинна, вы можете просмотреть каждую запись в словаре и выяснить, являются ли они перестановкой строки.Вы можете быть умнее - вы можете сортировать словарь и пропускать определенные записи.

Answer 3

Вы должны положить слова в три. Затем вы можете искать слово, когда вы генерируете перестановки. Вы можете пропустить целые блоки перестановок с первой частью, не входящей в список.

http://en.wikipedia.org/wiki/Trie

Answer 4

Почему вы не используете хеш-карту для хранения словарных слов? Таким образом, вы получите 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

Answer 5

Вы можете построить карту из отсортированного списка символов в список слов.

Например, с учетом этих:

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)

ВВ этом небольшом примере у нас нет совпадения, но для конкретного слова вы бы отсортировали его внутри, и с этим в качестве ключевого взгляда на вашу карту.

Answer 6

Другим простым решением может быть алгоритм, приведенный ниже,

1) Используйте "next_permutation", чтобы найти уникальную перестановку.

2) Используйте "find / find_if", чтобы найти ее в словаре.