使用哈希表和/或尝试的Anagram算法
我一直在互联网上搜索一段时间,找到一个字符串(单词)的所有字符串(即团队产生单词tame),使用哈希表和trie。 我在SO上找到的所有内容都是validation2个单词是字谜。 我想更进一步,找到一个英文算法,以便我可以用Java编程。
例如,
- 循环遍历所有角色。
- 对于每个唯一字符插入哈希表。
- 等等。
我不想要一个完整的程序。 是的,我正在练习面试。 如果出现这个问题,那么我就会知道它并且知道如何解释它而不仅仅是记住它。
由于“编程珍珠”一书引用的一些人最简洁的答案是(释义):
“按照这种方式排序(从左到右水平挥动),然后那样(从上到下垂直挥手)”
这意味着,从一列表(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分区。 这将为您提供恒定的因子加速,因为您只需要在一个分区内进行二进制搜索。 尝试是一种不同的优化方法,通过帮助您避免进行太多的字符串比较,您可以为特里结构中的每个终端挂起表的相应部分的第一行的索引。
哈希表不是最佳解决方案,因此我怀疑您是否需要使用它们。
找到anagram对(我知道)的最简单方法如下:
地图字符如下:
a – > 2 b – > 3 c – > 5 d – > 7
等等,使得字母a..z映射到前26个素数。
将单词中每个字符的字符值相乘,我们称之为“anagram数字”。 很容易看出TEAM和TAME会产生相同的数字。 实际上,当且仅当它们是字谜时,两个不同单词的字谜值才是相同的。
因此,在两个列表之间找到字谜的问题减少到找到出现在两个列表上的字谜值。 这可以通过按字母数字排序每个列表并在nlog(n)次中逐步查找公共值来轻松完成。
-
String
到char[]
- 排序
char[]
- 从排序的
char[]
生成String
- 使用它作为
HashMap
> - 将当前原始String插入到关联的值列表中
例如
它会有car, acr, rca, abc
acr: car, acr, rca abc: abc