algorithm - 如何在字符串中找到字谜频率？

Question

给定一个任意长度的字符串值，您应该确定彼此是字谜的单词的频率。

public static Map<String, Integer> generateAnagramFrequency(String str)
{ ... }

例如：如果字符串是“find art in a rat for cart and dna trac”，你的输出应该是一张地图：find -> 1 art -> 2 in -> 1 a -> 1 cart -> 2 and -> 2

键应该是单词的第一次出现，数字是该单词的字谜数，包括它本身。

我想出的解决方案是对所有单词进行排序并比较两个字符串中的每个字符，直到任一字符串的结尾。这将是 O(logn)。我正在寻找其他一些不会改变被比较的两个字符串的有效方法。谢谢。

Answer 1

我在Extract keyphrases from text (1-4 word ngrams)中编写了一个创建 n-gram（单词分析）的 JavaScript 实现。

可以轻松更改此功能以分析字谜的频率：
替换s = text[i];为s = text[i].sort()，以便字符的顺序不再重要。

Answer 2

通过按字母顺序对每个单词进行排序，为每个单词创建一个“签名”。按他们的签名对单词进行排序。依次遍历排序列表；如果签名与前一个签名相同，则您有一个字谜。