LeetCode 79 Word Search（单词查找）

二维字符表中查找单词是否存在，回溯法

题目链接:https://leetcode.com/problems/word-search/#/description

给出一个二维字符表，并给出一个String类型的单词，查找该单词是否出现在该二维字符表中。

For example,

Given board =

word = <code>"ABCCED"</code>, -&gt; returns <code>true</code>,

word = <code>"SEE"</code>, -&gt; returns <code>true</code>,

word = <code>"ABCB"</code>, -&gt; returns <code>false</code>.

同样还是使用第78题的方法，也就是回溯法求解。

通过上述例子，每次都是只能查找当前位置的上下左右四个位置（最多是四个位置，还有边界情况）。当查找到该单词的某个位置时，通过计数器不断更新当前已经匹配的字符的个数。

通过移动查找的坐标(row,col)来进行对一棵树的深度遍历操作。也就是dfs遍历操作。

调用dfs遍历的循环是有两层的。每次当遍历的一棵子树到叶子节点时，重新进入原始的循环体。更新树的遍历根节点。

因此循环体为

需要考虑递归函数的出口问题：因为需要对单词中的每个字符进行匹配操作，所以设置计数器用来统计当前所匹配的字符个数，同时也可以使用该变量来得到接下来要匹配的单词的字符。

如果给计数器个数等于单词的长度时，说明单词的所有字符都可以在表中找到，此时返回结果为true

如果当前的位置上下左右四个cell都不能与单词的字符进行匹配时，此时递归函数应退出并放回结果为false;

上面考虑了递归函数的出口问题，下面是对整个问题的结果进行讨论。

当有一个位置能够查找到目标单词的所有字符时就应该返回true，

当遍历开始位置从(0,0)到(board.row, board.col)结束都没有查找到时，返回false；

根据上述分析，得到以下参考代码：