Как я могу ускорить этот алгоритм анаграммы

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

Алгоритм берет любое количество букв, включая повторы, и находит самые длинные слова, составленные из его букв, используя каждую букву только один раз. Я также заинтересован в быстром нахождении лучших результатов, и меня не особо интересуют нижние (более короткие) результаты, пока выполняется N. Например:

STACK => stack, tacks, acts, cask, cast, cats…

Я погуглил и нашел несколько алгоритмов, и я придумал один, который, как мне казалось, был бы эффективным, но не настолько эффективен, как мне хотелось бы.

У меня есть предварительный справочный словарь. -сделано, которое сопоставляет отсортированный ключ с реальными словами, которые генерируют этот ключ.

"aelpp" => ["apple", "appel", "pepla"]

Я дополнительно разделил каждый словарь на разные в зависимости от длины ключа. Таким образом, ключи длиной 5 букв находятся в одном словаре, ключи длиной 6 букв - в другом. Каждый из этих словарей находится в массиве, в котором индекс - это длина ключей, найденных в словаре.

anagramArray[5] => dictionary5
dictionary5["aelpp"] => ["apple", "appel", "pepla"]

Мой алгоритм начинается с ввода входного слова « lappe », и он сортирует его :

"lappe" => "aelpp"

Теперь для каждого словаря, который содержит не более 5 букв, я провожу сравнение, чтобы извлечь его. Вот псевдокод:

word = input.sort
for (i = word.length; i > 0; i--)
    dictionaryN = array[i]
    for (key in dictionaryN)
        if word matches key
            add to returnArray
        end
    end
    if returnArray count > N
      break
    end
end

returnArray.sort by longest word, alphabetize

В словаре всего около 170 000 слов, но поиск занимает до 20 секунд для ввода 12 букв. Мой метод match создает регулярное выражение из ключа:

"ackst" => /a.*c.*k.*s.*t.*/

, так что, например, четырехбуквенный ключ, такой как acst (действует), будет соответствовать ackst (стек), потому что:

"ackst" matches /a.*c.*s.*t.*/

Я видел, как другие приложения делали то же самое за гораздо меньшее время, и мне интересно, является ли мой подход мусором или просто требует некоторой настройки.

Как я могу добиться максимальной вычислительной эффективности для создания первых N анаграмм из слова, отсортированных по максимальной длине?