单词搜索迷宫（Word Search Puzzle）问题的输入是一个二维的字符数组和一组单词，目标是找出字符数组网格中的所有单词。这些单词可以是水平的、垂直的或者是任意的对角线方向，所以需要查找8个不同的方向。如下图的网格：
这里面共有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的代码是：
public int Solve()
{
int matches = 0;
for (int rowIndex = 0; rowIndex < rows; rowIndex++)
{
for (int colIndex = 0; colIndex < columns; colIndex++)
{
for (int rd = -1; rd <= 1; rd++)
{
for (int cd = -1; cd <= 1; cd++)
{
if (rd!= 0 || cd != 0)
{
matches += SolveDirection(rowIndex, colIndex, rd, cd);
}
}
}
}
}return matches;
}
这里通过rd和cd来表示行和列的变化方式，如当rd=0，cd=1，表示向右检查；当rd=-1，cd=-1，表示向左上方检查。rd和cd的取值都是-1、0、1，共有9中组合，除了(0, 0)，正好可以表示8个方向。
SolveDirection返回在指定位置的某个方向上找到了几个单词：
private int SolveDirection(int baseRow, int baseCol, int rowDelta, int colDelta)
{
string charSequence = theBoard[baseRow, baseCol].ToString();
int matches = 0;
int searchResult = 0;for (int i = baseRow + rowDelta, j = baseCol + colDelta;
i >= 0 && j >= 0 && i < rows && j < columns;
i += rowDelta, j += colDelta)
{
charSequence += theBoard[i, j];
searchResult = PrefixSearch(words, charSequence);if (searchResult < 0 || searchResult >= words.Length)
{
// No word with this prefix
break;
}if (words[searchResult].Equals(charSequence))
{
matches++;
Console.WriteLine("Found '{0}' at [{1}, {2}] to [{3}, {4}]",
charSequence, baseRow, baseCol, i, j);
}
}return matches;
}
通过for循环来检查这个方向上的所有单词，这里使用了前面提到的前缀检查，来避免不必要的查找。
对于PrefixSearch来说，虽然从名字来看，它查找的是前缀，但也包含了完全匹配的情况：
private static int PrefixSearch(string[] a, string x)
{
int index = Array.BinarySearch(a, x, new StringPrefixComparer());
return index;
}
这里调用了Array.BinarySearch方法，如果不提供一个comparer，它会使用默认的字符串比较，所以这里创建一个StringPrefixComparer：
internal class StringPrefixComparer : IComparer<string>
{
public int Compare(string x, string y)
{
if (x.StartsWith(y))
{
return 0;
}
else
{
return x.CompareTo(y);
}
}
}
如果以此为前缀的单词不存在，直接结束循环；如果以此为前缀的单词存在，就顺便检查下该前缀是否恰好匹配一个单词。至此，这个小puzzle就完成了。类的完整代码在这里。
单词列表文件里包含下面几个单词：
Word List
above
fat
flow
test
that
this
tweak
two
wcg
wow
可以这样调用Solve方法：
WordSearchPuzzle puzzle = new WordSearchPuzzle("puzzle.txt", "words.txt");
puzzle.Solve();
那么对于上面的网格，返回结果是：
Found 'this' at [0, 0] to [0, 3]
Found 'two' at [0, 0] to [2, 0]
Found 'fat' at [3, 0] to [1, 2]
Found 'that' at [3, 3] to [0, 0]
Array.BinarySearch方法
实际上，上面的StringPrefixComparer是可以省略的。直接使用Array.BinarySearch本身就够了。将SolveDirection和PrefixSearch改为：
private static int PrefixSearch(string[] a, string x)
{
int index = Array.BinarySearch(a, x);
return (index >= 0) ? index : ~index;
}private int SolveDirection(int baseRow, int baseCol, int rowDelta, int colDelta)
{
string charSequence = board[baseRow, baseCol].ToString();
int matches = 0;
int searchResult = 0;for (int i = baseRow + rowDelta, j = baseCol + colDelta;
i >= 0 && j >= 0 && i < rows && j < columns;
i += rowDelta, j += colDelta)
{
charSequence += board[i, j];
searchResult = PrefixSearch(words, charSequence);// No words with this prefix.
if (searchResult == words.Length)
{
break;
}
if (!words[searchResult].StartsWith(charSequence))
{
break;
}if (words[searchResult].Equals(charSequence))
{
matches++;
Console.WriteLine("Found '{0}' at [{1}, {2}] to [{3}, {4}]",
charSequence, baseRow, baseCol, i, j);
}
}return matches;
}
也可以完成功能。原因是对于Array.BinarySearch方法来说，如果没有查找到，它不会直接返回-1。看上面的单词列表，如果查找this，会返回5，因为它刚好有匹配值；如果查找th，将返回-5，这个-5是列表中第一个大于th的项（that）的索引（4）的按位取补；如果查找的是wt，则返回-10，wt大于列表中所有项，-11即最后一项的索引（9）加一的按位取补。这样如果BinarySearch的结果是[0-9]，说明找到了匹配值；如果小于零，则按位取补返回，取补的结果为列表长度，说明该字符串大于每个单词，不可能有匹配，返回，否则检查该字符串是否为前缀。
以前没有注意到Array.BinarySearch的这个特性，原来它还有此用处:)
好了，现在可以放松一下，玩玩游戏了。
参考：
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。