0

这是一个任务。

我有一个哈希表（链表数组），其中包含来自英语词典的一堆单词。

我还有一个最大为 100 x 100 的二维字母数组，但我现在只显示 3x3：

[a][b][c]
[g][a][c]
[b][t][a]

与任何单词搜索一样，单词可以水平、垂直、对角和向后排列。

我在这里只展示了一个小网格，但是如果我有一个更大的网格，也会有更大的单词。

我如何在数组中找到单词？看起来我在这里只需要“bat”和“cab”。想象一下，我们有一个更大的网格，单词最多可以包含 20 个字母。这就是我能想到的：

  1. 从网格上的某个地方开始
  2. 检查 2 个字母的单词
  3. 检查所有 8 个方向
  4. 将您找到的任何内容放入哈希表中以检查匹配项
  5. 重复步骤 2，除了 3、4、5、6、7、8、9、10 个字母的单词
  6. 返回第 1 步，在网格上移动一个位置并重复

似乎是一种非常愚蠢的做法。

4

1 回答 1

1

哈希表

最简单（虽然不是特别有效）的方法是简单递归。

对于每个单元格，递归地环顾四周，跟踪当前单词，并在每一步检查当前单词是否包含在哈希表中。

set up hash table with all words

for each cell c
  findWords(c, c.value)

findWords(cell c, string current)
  if current.length > longestWord
    return
  if hashTable.contains(current)
    output current
  for each neighbour n of c
    findWords(n, current + c.value)

现在，为了提高效率，我们基本上可以模拟一个trie。

我们会将每个单词的所有前缀放入哈希表中，因此对于"johnny"，您将在哈希表中拥有"j", "jo", "joh", "john","johnn"和"johnny"。

我们可以只在哈希表中有一个标志来指示给定条目是否是有效单词。因此，对于上述"johnny"情况，只有这个标志。

set up hash table with all words, but also all prefixes of words

for each cell c
  findWords(c, c.value)

findWords(cell c, string current)
  if hashTable.contains(current)
    if isValidWord(current)
      output current
    for each neighbour n of c
      findWords(n, current + c.value)

特里

对于这个问题， trie似乎是一种更好的数据结构。

首先，用所有的词构建树。然后，对于网格上的每个位置，检查是否存在从根开始的边作为其值。如果有，递归检查它的每个邻居，检查该值是否有边，检查它的邻居，等等。

伪代码是这样的：

set up trie with all words

for each cell c
  if root.hasChild(c.value)
    findWords(root.getChild(c.value), c)

findWords(node n, cell c)
  if n.isValidWord
    output n.getWord
  for each neighbour ne of c
    if n.hasChild(ne.value)
      findWords(n.getChild(ne.value), ne)
于 2013-10-22T09:09:20.650 回答