Для данной строки найдите все ее перестановки, которые являются словом в словаре.

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

Для данной строки найдите все ее перестановки, которые являются словом в словаре.

Мое решение:

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

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

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