1.问题描述

        给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。        

        单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

        示例1

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

        示例2 

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

        示例3 

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

        提示

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

        难度等级

        中等

        题目链接

        单词搜索

2.解题思路

        这道题要我们在一个矩阵中搜索单词，单词必须按照字母的顺序，通过相邻的单元格内的字母构成。

        这道题，在正式开始解题之前，我们可以将一些不可能的情况排除在外。

        首先，如果我们在搜索的时候，如果索引越界了，那肯定是不行的，所以我们可以先解决一个判断索引是否越界的问题，行列索引要大于等于0同时小于行列索引的最大值。

java">    //判断是否越界public boolean isOutOfIndex(int x,int y,int boardX,int boardY){return x >= 0 && y >=0 && x < boardX && y < boardY;}

        接着，如果说我们单词中的某个字母的个数，比题目提供给我们的board里面的个数还多，那肯定是搜索不到这个单词的。比如我们要找"aaa"，但是board中只有两个a，那我们肯定也是找不到的。

        所以我们可以先统计一下board中每个字符的个数和word中每个字符的个数，并将它们进行比较，如果出现我们上面提到的情况，直接返回找不到的结果就好了。

java">        //检查board中单个字符的个数是否比word中少，如果少，肯定不存在int[] wordCount = new int[128];int[] boardCount = new int[128];//统计board中的字符个数for(char[] bo : board){for(char c : bo){boardCount[c]++;}}//统计word中的字符个数并进行比较for(char c : word.toCharArray()){wordCount[c]++;//判断board中单个字符的个数是否比word少if(wordCount[c] > boardCount[c]){return false;}}

        然后我们可以通过遍历board，找到word单词的首个字符在board中的位置，然后从这个位置出发进行搜索，看能不能找到完整的一个word单词。值得注意的是，board中同一个字符可能出现多个，所以当某一个位置的字符找不到完成的单词时，不代表其他位置的字符不行，所以要将整个board都找一遍，除非我们已经找到了。

java">        boolean flag = false;//遍历board，找到word的第一个字符for(int i = 0;i < board.length;i++){for(int j = 0;j < board[0].length;j++){if(board[i][j] ==word.charAt(0)){flag = dfs(board,0,i,j,word);//找到了if(flag == true){return flag;}}}}//没找到，返回falsereturn flag;

        接下来，就是我们核心的搜索方法了，这里我们采用递归的深度搜索。我们通过一个索引index来标记我们找打了word中的第几个字符，同时我们还要传入当前搜索的坐标，以及board和word。

java">    public boolean dfs(char[][] board,int index,int x,int y,String word)

        确定了需要用到的参数之后，我们就可以来判断搜索结束的条件了。如果index等于word的长度了，说明我们已经找到了word的最后一个字符，找到了完整的word单词，返回true；如果还没有找到，就可以判断我们搜索的坐标是否越界，也就是我们一开始干的事情，调用那个判断是否越界的方法进行判断，如果越界了，直接返回false。

java">        //判断是否已经找到wordif(index == word.length()){return true;}//判断坐标是否越界if(!isOutOfIndex(x,y,board.length,board[0].length)){return false;}

        确定完坐标没有越界之后，我们就可以正式进行搜索了。判断board当前位置的字符是否为我们要找到第index个字符，如果不是，直接返回false结束这次的搜索。如果是我们要寻找的字符，将board当前位置的字符用一个临时变量存储起来，并将当前位置设置为0，用来标记被成功搜索到了。接着，我们向上下左右相邻单元格进行搜索，只要有其中一个方向走的通，就是可以返回true，完成四个方向的搜索之后，我们要记得将board当前的位置恢复，这就是我们要用临时变量存储起来的原因，避免本次搜索全部失败，但该位置会是其他搜索成功的关键因素的情况。将字符恢复之后，直接返回搜索结果就可以了。

java">        //判断坐标是否越界if(!isOutOfIndex(x,y,board.length,board[0].length)){return false;}//判断当前坐标是否为我们要找的第index个字符if(word.charAt(index) != board[x][y]){return false;}//将当前字符设置为0,标记为已被访问,后面需要将字符恢复char temp = board[x][y];board[x][y] = '0';//递归查找其他方向boolean flag = dfs(board,index+1,x-1,y,word) || dfs(board,index+1,x+1,y,word)||dfs(board,index+1,x,y-1,word)||dfs(board,index+1,x,y+1,word);//将字符恢复,避免影响其他方向的搜索board[x][y] = temp;//返回结果return flag;

        如果我们遍历完整个board数组之后，仍然没有找到，直接返回false没找到即可。

        这道题基本到这就结束了，但是我们还可以做一个小优化，就是在正式遍历board数组之前，我们可以像判断word的最后一个字符在word中出现的个数是否小于word的第一个字符在board中出现的个数，那我们可以将word翻转之后再进行搜索。因为如果word的第一个字符在board中出现的个数多，那我们搜索失败的次数也就会随之增多，因为极大的可能是那么多位置中只有一个是可以搜索成功的。

java">        //word中最后一个字符的个数小于board中word的第一个字符的个数,可以将字符反转减少递归的次数if(wordCount[word.charAt(word.length()-1)] < boardCount[word.charAt(0)]){word = String.valueOf(new StringBuffer(word).reverse());}

3.代码展示

java">class Solution {public boolean exist(char[][] board, String word) {//检查board中单个字符的个数是否比word中少，如果少，肯定不存在int[] wordCount = new int[128];int[] boardCount = new int[128];//统计board中的字符个数for(char[] bo : board){for(char c : bo){boardCount[c]++;}}//统计word中的字符个数并进行比较for(char c : word.toCharArray()){wordCount[c]++;//判断board中单个字符的个数是否比word少if(wordCount[c] > boardCount[c]){return false;}}//word中最后一个字符的个数小于board中word的第一个字符的个数,可以将字符反转减少递归的次数if(wordCount[word.charAt(word.length()-1)] < boardCount[word.charAt(0)]){word = String.valueOf(new StringBuffer(word).reverse());}boolean flag = false;//遍历board，找到word的第一个字符for(int i = 0;i < board.length;i++){for(int j = 0;j < board[0].length;j++){if(board[i][j] ==word.charAt(0)){flag = dfs(board,0,i,j,word);//找到了if(flag == true){return flag;}}}}//没找到，返回falsereturn flag;}public boolean dfs(char[][] board,int index,int x,int y,String word){//判断是否已经找到wordif(index == word.length()){return true;}//判断坐标是否越界if(!isOutOfIndex(x,y,board.length,board[0].length)){return false;}//判断当前坐标是否为我们要找的第index个字符if(word.charAt(index) != board[x][y]){return false;}//将当前字符设置为0,标记为已被访问,后面需要将字符恢复char temp = board[x][y];board[x][y] = '0';//递归查找其他方向boolean flag = dfs(board,index+1,x-1,y,word) || dfs(board,index+1,x+1,y,word)||dfs(board,index+1,x,y-1,word)||dfs(board,index+1,x,y+1,word);//将字符恢复,避免影响其他方向的搜索board[x][y] = temp;//返回结果return flag;}//判断是否越界public boolean isOutOfIndex(int x,int y,int boardX,int boardY){return x >= 0 && y >=0 && x < boardX && y < boardY;}
}

4.总结

        这道题要写出来不难，但是要减少搜索时间还是有一点难度的，统计word的字符个数和board进行比较和将word的字符串翻转的情况，没有做过类似的题的话，应该挺难想到的。好了，这道题就啰嗦到这里，祝大家刷题愉快~