在字符串列表中搜索的高效快捷方法

一种字典,其关键字是单词的排序版本:

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] 。

效率:查询运行 in average in O(1) time 。

对于大字符串,您将有 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