Есть способы ускорить вашу функцию проверки анаграммы.Самгак указал один.Другая очевидная оптимизация - возвращать false, если слово длиннее, чем количество доступных букв плюс пробелы.В конце концов, это все микрооптимизации, и в итоге вы проверите весь словарь.
Вы сказали, что рассматривали возможность использования trie.На мой взгляд, это хорошее решение, потому что структура этого слова заставит вас проверять только соответствующие слова.Создайте это так:
- Сортируйте буквы каждого слова, чтобы «треугольник» и «интеграл» оба стали «aegilnrt».
- Вставьте отсортированное слово в три.
- Если вы поместите конечный маркер в обычном дереве, вы поместите список возможных слов.
Если вы искали точные анаграммы, вы бы отсортировали словочтобы проверить, проследить три и распечатать список возможных анаграмм в конце.Но здесь вам приходится иметь дело с частичными анаграммами и пробелами:
- Регулярный обход означает, что вы берете следующую букву слова и затем спускаетесь по соответствующей ссылке в дереве, если она существует.
- Частичные анаграммы можно найти, игнорируя следующую букву, не убирая в дереве.
- С пробелами можно справиться, опустив все возможные ветви дерева и уменьшив количество пробелов.
Если у вас есть пробелы, вы получите дубликаты.Например, если у вас есть буквы A, B и C и пустая плитка, вы можете сделать слово CAB, но вы можете получить его четырьмя различными способами: CAB, _AB, C_B, CA _.
Выможно обойти это, сохранив список результатов в структуре данных, которая исключает дубликаты, такие как набор или упорядоченный набор, но вам все равно придется идти по одному и тому же пути несколько раз, чтобы создать дубликаты.
AЛучшее решение состоит в том, чтобы отслеживать, какие узлы Tree вы посетили, с какими параметрами, т.е. с оставшимися неиспользованными буквами и пробелами.Вы можете сократить такие пути.Вот реализация в псевдокоде:
function find_r(t, str, blanks, visited)
{
// don't revisit explored paths
key = make_key(t, str, blanks);
if (key in visited) return [];
visited ~= key;
if (str.length == 0 and blanks == 0) {
// all resources have been used: return list of anagrams
return t.word;
} else {
res = [];
c = 0;
if (str.length > 0) {
c = str[0];
// regular traversal: use current letter and descend
if (c in t.next) {
res ~= find_r(t.next[c], str[1:], blanks, visited);
}
# partial anagrams: skip current letter and don't descend
l = 1
while (l < str.length and str[l] == c) l++;
res ~= find_r(t, str[l:], blanks, visited);
}
if (blanks > 0) {
// blanks: decrease blanks and descend
for (i in t.next) {
if (i < c) {
res ~= find_r(t.next[i], str, blanks - 1, visited);
}
}
}
return res;
}
}
(Здесь ~ обозначает конкатенацию списка или вставку набора; [beg=0:end=length] обозначает фрагменты строки; in проверяет, содержит ли словарь или набор ключ.)
После того как вы построили дерево, это решение быстро, когда нет пробелов, но оно экспоненциально ухудшается с каждым пробелом и с большими пулами букв.Тестирование с одним пробелом все еще достаточно быстрое, но с двумя пробелами оно соответствует вашему существующему решению.
Теперь в игре «Скрэббл» не более двух пробелов, а стойка может содержать до семи плиток.так что на практике это может быть не так плохо.Другой вопрос, должен ли поиск учитывать слова, полученные с двумя пробелами.Список результатов будет очень длинным и будет содержать все двухбуквенные слова.Игрок может быть более заинтересован в словах с высокими показателями, которые можно воспроизвести одним пробелом.