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

Question

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

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

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

会变成

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

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

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

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

Given an input string how to search for all the anagrams in O(k logN + W) time where W is the output size and k is the max characters in the string?

python

binary-search

anagram