python - 给定一个输入字符串，如何在 O(k logN + W) 时间内搜索所有变位词，其中 W 是输出大小，k 是字符串中的最大字符数？

Question

我正在尝试编写一个程序，在给定用户输入字符串的情况下找到列表中所有可用的字谜？ O(klogN + W ) 时间复杂度不包括排序的时间复杂度。

我的方法是先按字母顺序对每个单词进行排序，然后再按字母顺序对列表进行排序。例如，像这样的列表:

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

会变成

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

为了满足 O(klogN) 的时间复杂度，我决定使用二分查找。但我不确定如何真正去做？到目前为止，这是我当前的代码，但它只将单词的第一个 anagram 附加到 anagramList？

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

areAnagrams 检查 2 个字符串是否是彼此的变位词。

Answer 1

对每个单词中的字符进行排序可能是正确的方法，但您需要存储原始单词并将每个已排序 字符序列映射到一个或多个单词的列表，因此您可以显示所有有效结果。您将需要这样的映射(左边是一个排序的字符序列，右边是所有有效的单词，它们是这些字符的字谜):

"art" -> [ "art", "rat" ]
"acr" -> [ "car" ]

...

一旦你有了这个映射，你就可以通过二分查找或直接使用 Python 的散列机制来搜索它，方法是使用 Python dict 对象(对于大小为 N 的字典，不是二进制搜索的效率低于 log2(N)，并且在解释器中编码，因此非常快。

构建字典后，查找变位词需要对输入序列进行排序(最坏情况下，O(k))，然后找到匹配的字符串 (O(log(N))，用于二进制搜索)。它根本不依赖于输出大小(输出已经在每个字典条目中准备好了)。

如果您决定不使用 dict 并坚持使用二进制搜索，那么最好的数据结构很可能是列表的列表，每个元素包含 ["sorted-characters", "word1 ", "word2", ...等]。外部列表按每个内部列表中的第一项(排序的字符)排序，例如，上面的示例字谜:

["art", "art", "rat" ]
["acr", "car" ]