单词搜索迷宫（Word Search Puzzle）问题的输入是一个二维的字符数组和一组单词，目标是找出字符数组网格中的所有单词。这些单词可以是水平的、垂直的或者是任意的对角线方向，所以需要查找8个不同的方向。如下图的网格：
| 0 | 1 | 2 | 3 | |
| 0 | t | h | i | s |
| 1 | w | a | t | s |
| 2 | o | a | h | g |
| 3 | f | g | d | t |
这里面共有4个单词：this（[0, 0]-[0, 3]）、two（[0, 0]-[2, 0]）、fat（[3, 0]-[1, 2]）和that（[3, 3]-[0, 0]），其它更短的单词此处没有列出。
问题分析
最直接的方法就是，使用蛮力算法逐一检查每个可能的字符串是否在单词表中，就像我们用眼睛去检查那样，可以描述为：
for each row R
for each column C
for each direction D
check if word W in wordList
假设单词列表wordList有40个单词，16×16的网格，需要大约80000（16*16*8*40）次检查，这种方法还是可行的。但如果wordList扩展到整部字典，比如有40000个单词，那工作量不小了（考虑到每个方向上，可能的单词都会有多个；而且每次都要在40000个单词里查找）。此时再采用线性查找，就不靠谱了，所以考虑将wordList按字典顺序存储，采用二分查找，这样对于每个可能的单词最多16次比较就可以了。
进一步观察，假定某方向上检查到字符串qx，词典里没有以qx开头的单词，此时可以确定这个方向不需要进一步检查了。
剩下的问题是，怎样检查8个方向的单词呢？来看位于[0, 0]处的字符t（这里忽略掉所有的单字符单词，所以一个字符本身不会构成单词），向右检查，终点的位置分别是[0, 1]，[0, 2]，[0, 3]，即行索引不变，列索引递增；向右下方向检查，终点的位置分别是[1, 1]，[2, 2]，[3, 3]，即行索引、列索引同时递增。每个方向都是如此，这样我们找出每个方向上行索引、列索引的变化规律来，就容易实现了。
实现
现在通过上面分析到的二分查找、前缀检查和方向检查，基本上可以按思路直接写出来。创建类WordSearchPuzzle来完成功能，它的基本方法有：
在构造函数里，读取puzzle网格board和单词列表words，然后通过Solve方法进行检查，它会借助于SolveDirection和PrefixSearch方法。Solve的代码是：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/41925.html