给定一个输入字符串,如何在O(k logN+W)时间内搜索所有anagrams,其中W是输出大小,k是字符串中的最大字符?

我试图编写一个程序,由用户给定一个输入字符串,查找列表中所有可用的anagram?O(KLogn+W)时间复杂度不包括排序的时间复杂度。

我的方法是先按字母顺序排列每个单词,然后按字母顺序排列列表。例如,这样的列表:

['act',bad','cat','tac']... 

会变成

['act','act','act','bad']

为了满足O(KLogn)时间复杂度,我决定使用二进制搜索。但我不知道该怎么做?到目前为止,这是我的当前代码,但它只在anagramList后面附加单词的第一个anagram?

def binarySearch(arr, lower, upper, target):
anagramList=[]
if upper >= lower:
    mid = lower + ((upper - lower) // 2)
    if areAnagrams(arr[mid],target):
        anagramList.append(arr[mid])
    elif arr[mid] > target:
        return binarySearch(arr, lower, mid - 1, target)
    else:
        return binarySearch(arr, mid + 1, upper, target)
return anagramList

区域图检查两个字符串是否相互为anagram。