如何在给定用户输入的O(logN)时间内搜索anagram?

嗨,我已经想了好几天了。

我正在尝试实现一个程序,将字典读入列表并对其进行排序 O(N) O(对数N) 时间。我可以按字母对每个单词进行排序,并按O(N)的字母顺序对列表进行排序。

例如,“act”是anagram组“act”、“cat”和“tac”的键。

arr=['act','cat','tac','bad','fad'] 

排序后

[['act', 'act'], ['cat', 'act'], ['tac', 'act'], ['bad', 'abd'],  ['fad', 'adf']] 

但是二进制搜索只找到一个目标,所以它只会为'act'下的anagram group返回'tac'。我的二进制搜索代码:

def binarySearch(arr, lower, upper, target):
anagramList=[]
if upper >= lower:
    mid = lower + ((upper - lower) // 2)
    if areAnagrams(arr[mid][1],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

我试着把他们这样分组

[['act','act','cat','tac'],['bad','abd'],['fad','daf]]

但是它需要O(N^2)的复杂度比O(N)大?有人能建议我怎么做吗?谢谢。

编辑: 例如,如果查询字符串是alppe,则输出将包含单词appel和apple。