Эффективный и быстрый способ поиска в списке строк

Question

Следующая функция возвращает количество слов из списка, которые содержат те же символы, что и введенное слово. Порядок символов в словах не важен. Однако, скажем, есть список, который содержит миллионы слов. Какой самый эффективный и быстрый способ выполнить этот поиск?

Пример:

words_list = ['yek','lion','eky','ekky','kkey','opt'];

если мы сопоставим слово «ключ» со словами в списке, функция вернет только «yek» и «eky», так как они имеют одни и те же точные символы с «ключом» независимо от порядка.

Ниже приведена функция, которую я написал

def find_a4(words_list, word):
    # all possible permutations of the word that we are looking for
    # it's a set of words 
    word_permutations = set([''.join(p) for p in permutations(word)])
    word_size = len(word)
    count = 0

    for word in word_list:
        # in the case of word "key", 
        # we only accept words that have 3 characters 
        # and they are in the word_permutations 
        if len(word) == word_size and word in word_permutations:
            count += 1

    return count

Answer 1

Для большой строки у вас будет n! перестановок для поиска. Я отсортирую все строки перед сравнением, это будет nlog (n), и будет сортировать и сравнивать только при совпадении длин -

def find_a4(words_list, word):
    word = ''.join(sorted(word))
    word_size = len(word)
    count = 0
    for word1 in words_list:
        if len(word1) == word_size:
            if word == ''.join(sorted(word1)):
                count += 1
    return count 

Answer 2

Словарь, ключом которого является отсортированная версия слова:

word_list = ['yek','lion','eky','ekky','kkey','opt']

from collections import defaultdict
word_index = defaultdict(set)

for word in word_list:
    idx = tuple(sorted(word))
    word_index[idx].add(word)

# word_index = {
#    ('e', 'k', 'y'): {'yek', 'eky'},
#    ('i', 'l', 'n', 'o'): {'lion'},
#    ('e', 'k', 'k', 'y'): {'kkey', 'ekky'},
#    ('o', 'p', 't'): {'opt'}
# }

Тогда для запроса вы должны сделать:

def find_a4(word_index, word):
    idx = tuple(sorted(word))
    return len(word_index[idx])

Или, если вам нужно вернуть фактические слова, измените его на return word_index[idx].

Эффективность: запросы выполняются в среднем за O (1) время .