0

我一直在互联网上搜索一段时间，寻找使用哈希表和特里树查找字符串（单词）的所有字谜（即团队产生单词 tame）的步骤。我在这里找到的只是验证 2 个单词是字谜。我想更进一步，找到一个英文算法，以便我可以用 Java 对其进行编程。

例如，

  • 循环遍历所有字符。
  • 对于每个唯一字符插入哈希表。
  • 等等。

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

4

3 回答 3

4

哈希表不是最好的解决方案，所以我怀疑你会被要求使用它们。

查找字谜对（我知道）的最简单方法如下：

映射字符如下：

a -> 2 b -> 3 c -> 5 d -> 7

依此类推，字母 a..z 映射到前 26 个素数。

将单词中每个字符的字符值相乘，我们称之为“字谜数”。很容易看出 TEAM 和 TAME 会产生相同的数字。事实上，当且仅当它们是字谜时，两个不同单词的字谜值才会相同。

因此，在两个列表之间查找字谜的问题简化为找到两个列表上出现的字谜值。这很容易通过按字谜编号对每个列表进行排序并逐步找到共同值来完成，以 nlog(n) 次为单位。

于 2013-10-27T07:49:41.790 回答
4

由于“编程珍珠”书中引用的某个人的最简洁的答案是（释义）：

“以这种方式排序（从左到右水平挥手），然后以这种方式（从上到下垂直挥手）”

这意味着，从一个单列表 (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 个分区。这将为您提供恒定的加速因子，因为您只需在一个分区内进行二进制搜索。通过帮助您避免进行过多的字符串比较，尝试是一种不同的优化方式，您可以为 trie 中的每个终端的表的适当部分挂起第一行的索引。

于 2013-10-25T23:19:53.580 回答
0
  • String至char[]
  • 解决char[]
  • String从排序生成char[]
  • 用它作为关键HashMap<String, List<String>>
  • 将当前原始字符串插入关联的值列表

例如对于

car, acr, rca, abc它会有

acr: car, acr, rca
abc: abc
于 2013-10-25T22:40:40.193 回答