java - 使用哈希表和/或尝试的 Anagram 算法

Question

我在互联网上搜索了一段时间，寻找使用哈希表和 trie 查找字符串(单词)(即团队生成单词 tame)的所有变位词的步骤。我在这里找到的所有内容都是为了验证 2 个单词是字谜。我想更进一步，找到一个英文算法，以便我可以用 Java 对其进行编程。

例如，

• 遍历所有字符。
• 将每个唯一字符插入哈希表。
• 等等。

我不想要一个完整的程序。是的，我正在练习面试。如果出现这个问题，我会知道并知道如何解释它，而不仅仅是记住它。

Answer 1

“编程珍珠”一书中引用了一些人的最简洁的答案是(释义):

“这样排序(从左到右水平挥手)，然后再这样(从上到下垂直挥手)”

这意味着，从单列表 (word) 开始，创建一个两列表:(sorted_word, word)，然后在第一列对其进行排序。

现在要查找单词的变位词，首先计算排序后的单词并对其在表的第一列中的第一次出现进行二进制搜索，并在第一列相同的情况下读取第二列的值。

输入(不需要排序):

mate
tame
mote
team
tome

“这样”排序(水平):

aemt, mate
aemt, tame
emot, mote
aemt, team
emot, tome

“那样”排序(垂直):

aemt, mate
aemt, tame
aemt, team
emot, mote
emot, tome

查找“团队”->“aemt”

aemt, mate
aemt, tame
aemt, team

就哈希表/尝试而言，只有当您想要稍微加快查找速度时，它们才会出现。使用哈希表，您可以根据第一列的哈希将 2 列垂直排序的表划分为 k 个分区。这会给你一个常数因子加速，因为你必须只在一个分区内进行二进制搜索。 tries 是一种不同的优化方式，可帮助您避免进行过多的字符串比较，您可以为 trie 中的每个终端挂起表中适当部分的第一行的索引。