java - 搜索数组中的单词

Question

这个问题已经有答案了:

已关闭 10 年前。

Possible Duplicate:
How to find list of possible words from a letter matrix [Boggle Solver]

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

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

我需要将 ArrayList 与该数组进行匹配，以查找 ArrayList 中指定的单词。当搜索单词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) Not Acceptable ，因为位置 (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)无法匹配。

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

Answer 1

我认为您可能会花费大部分时间来尝试匹配网格不可能构建的单词。因此，我要做的第一件事就是尝试加快这一步，这应该能让您顺利完成任务。

我会将网格重新表示为一个可能的移动表，您可以通过字母进行索引。首先为每个字母分配一个数字(通常 A=0、B=1、C=2，...等等)。对于您的示例，我们只使用您拥有的字母的字母表(在第二个网格中，最后一行显示“m o f p ”):

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

然后创建一个 2D boolean 数组来告诉您是否有可用的特定字母转换:

     |  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

如果都允许，就有可能找到这个词。

例如，可以在第四次转换(m 到 e:helMEt)中排除单词“helmet”，因为表中的该条目是错误的。

并且可以排除“仓鼠”一词，因为不允许第一个(h 到 a)转换(甚至在您的表格中不存在)。

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

当你的手机应用程序完成时请告诉我! ;)