Какие существуют алгоритмы создания анаграмм из определенного набора букв?

Несколько алгоритмов для создания анаграмм из определённого набора букв:

1. Сортировка букв в каждом слове, а затем сравнение сортированных версий слов. 1 Этот алгоритм работает за O(n * log n) времени, где n — длина слова. 1
2. Использование хэш-таблицы или счётчика символов. 1 Для каждого слова создаётся словарь, в котором ключами являются символы, а значениями — их количество. 1 Затем словари сравниваются. 1
3. Преобразование входной строки в «пул символов». 5 Его можно реализовать в виде массива, где oc[c] — количество встречаемости символа c. 5 Затем используется алгоритм обратного отслеживания, чтобы найти слова, которые вписываются в кодировку. 5
4. Использование префиксного дерева (Trie). 4 Словарь добавляется в префиксное дерево, каждый узел которого содержит пару: буква + её количество в слове. 4 Узлы отсортированы по алфавиту и частоте буквы в слове. 4 Затем берётся слово, и ищутся узлы, начинающиеся на минимальную букву слова. 4 После нахождения такого узла в поддереве ищется путь, содержащий оставшиеся буквы в нужном количестве. 4