1

可能重复：
如何从字母矩阵中找到可能的单词列表 [Boggle Solver]

我有一个String[][]数组，例如

h,b,c,d
e,e,g,h
i,l,k,l
m,l,o,p

我需要将 ArrayList 与此数组进行匹配，以找到 ArrayList 中指定的单词。搜索 word时，我需要得到肯定匹配和字母的位置，hello例如在这种情况下(0,0), (1,1),(2,1)和。(3,1)(3,2)

当一个字母一个字母地查找时，我们假设我们成功地找到了第一个l字母，程序应该尝试在l它旁边的位置找到下一个字母（ ）。所以它应该匹配 e、e、g、k、o、l、m 和 i 表示它周围的所有字母：水平、垂直和对角线。在单词中找不到相同的位置两次，因此(0,0), (1,1), (2,1),(2,1)和(3,2)是不可接受的，因为该位置(2,1)匹配了两次。l在这种情况下，两者都将匹配单词，因为允许对角位置，但由于要求一个位置不能多次使用，所以它需要匹配另一个。

这种情况也应该匹配

h,b,c,d
e,e,g,h
l,l,k,l
m,o,f,p

如果我们假设我们尝试搜索helllo，它将不匹配。要么匹配，(x1, y1) (x1, y1)要么(x1, y1) (x2, y2) (x1, y1)无法匹配。

我想知道实现这种功能的最佳方式是什么。如果我String[][]在 ArrayList 中有 4x4 数组和 100 000 个单词，那么最有效和最简单的方法是什么？

4

4 回答 4

2

我认为您可能会花费大部分时间来尝试匹配您的网格不可能构建的单词。所以，我要做的第一件事就是尝试加快这一步，这应该能让你大部分时间到达那里。

我会将网格重新表达为您按字母索引的可能移动的表格。首先为每个字母分配一个数字（通常是 A=0、B=1、C=2、……等等）。对于您的示例，让我们只使用您拥有的字母的字母表（在第二个网格中最后一行读取“mofp”）：

 b | c | d | e | f | g | h | k | l | m |  o |  p
---+---+---+---+---+---+---+---+---+---+----+----
 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11

然后你创建一个二维布尔数组，告诉你是否有某个字母转换可用：

     |  0  1  2  3  4  5  6  7  8  9 10 11  <- from letter
     |  b  c  d  e  f  g  h  k  l  m  o  p
-----+--------------------------------------
 0 b |     T     T     T  T     
 1 c |  T     T  T     T  T
 2 d |     T           T  T
 3 e |  T  T     T     T  T  T  T
 4 f |                       T  T     T  T
 5 g |  T  T  T  T        T  T  T
 6 h |  T  T  T  T     T     T  T
 7 k |           T  T  T  T     T     T  T
 8 l |           T  T  T  T  T  T  T  T  T
 9 m |                          T     T
10 o |              T        T  T  T
11 p |              T        T  T
 ^
 to letter

现在浏览您的单词列表并将单词转换为转换（您可以预先计算）：

hello (6, 3, 8, 8, 10):
6 -> 3, 3 -> 8, 8 -> 8, 8 -> 10

然后通过在表中查找这些转换来检查是否允许这些转换：

[6][3] : T
[3][8] : T
[8][8] : T
[8][10] : T

如果它们都被允许，那么就有可能找到这个词。

例如，可以在第 4 次转换（m 到 e：helMEt）时排除单词“helmet”，因为表中的该条目是错误的。

并且可以排除仓鼠这个词，因为不允许第一个（h 到 a）转换（甚至不存在于您的表中）。

现在，对于您没有消除的剩余单词，请尝试按照您现在的方式或按照此处其他一些答案中的建议在网格中实际找到它们。这是为了避免由于网格中相同字母之间的跳跃而导致的误报。例如，表格允许使用“帮助”一词，但网格不允许使用“帮助”一词

当你的手机应用程序完成时让我知道！;)

于 2012-11-10T22:53:52.010 回答
0

一种调查方法是从网格中生成所有可能的字母（字符串）序列，然后检查每个单词是否存在于这组字符串中，而不是根据网格检查每个单词。例如，从h您的第一个网格开始：

h
hb
he
he // duplicate, but different path
hbc
hbg
hbe
hbe // ditto
heb
hec
heg
...

由于生成序列的开销，这对于非常大的单词列表可能会更快。对于小的单词列表，根据网格单独测试它们会快得多。

您要么需要存储整个路径（包括坐标），要么有一个单独的步骤来计算匹配单词的路径。哪个更快取决于命中率（即您在网格中实际找到的输入词的比例）。

根据您需要实现的目标，您也许可以将序列与字典单词列表进行比较，以在开始匹配之前消除非单词。

链接问题中的更新 2有几个有效的、快速的解决方案可以从网格生成序列，递归地加深以生成更长的序列。但是，他们针对从单词列表生成的 Trie 进行测试，这使他们能够尽早放弃序列的子树——这会修剪搜索并大大提高效率。这与 Markus 建议的转换过滤具有类似的效果。

于 2012-11-10T22:09:00.513 回答
0

虽然我确信在学术上对这个问题有一个美丽而有效的答案，但您可以使用相同的方法，但有一个列表可能性。因此，对于单词“hello”，当您找到字母“h”时，接下来您将添加可能的“e”字母，依此类推。每一种可能性都会形成一条字母的路径。

于 2012-11-10T22:14:27.917 回答
0

我首先将您的网格视为一个图形，其中每个网格位置都是一个节点，每个节点都连接到它的八个邻居（但是，您不需要在代码中将其显式编码为图形）。一旦找到潜在的起始字母，您需要做的就是从每个起始位置对图形进行深度优先搜索。关键是要记住你已经搜索过的地方，这样你就不会为自己做更多的工作（或者更糟糕的是，陷入一个循环）。

根据所使用的字符空间的大小，您还可以从构建查找表中受益。让我们假设英语（26 个连续字符代码点）；如果您从构建一个 26 元素List<Point>[]数组开始，您可以从网格中填充该数组一次，然后可以快速获取位置列表以开始搜索任何单词。例如，要获取h我会写的位置arr['h'-'a']

如果您应用相同的策略并为图中的每个边列表构建查找表，您甚至可以进一步利用这一点。不必为每个节点搜索所有 8 条边，您已经知道要搜索哪些边（如果有）。

（注意——如果你的字符空间不连续，你仍然可以做一个查找表，但你需要使用HashMap<Character,List<Point>>andmap.get('h')来代替。）

于 2012-11-10T23:06:43.357 回答