LeetCode 79 Word Search（单词查找）

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

 

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

 

For example,
Given board =

 

[['A','B','C','E'],['S','F','C','S'],['A','D','E','E'] ]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

 

 

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

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

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

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

因此循环体为

for(int i = 0 ; i < row ; i++){for(int j = 0 ; j < col ; j++){dfs();// calling the function to go through the tree}
}

 

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

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

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

 

 

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

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

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

 

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

package leetcode_100;/**** * @author pengfei_zheng* 二维字符表中查找单词*/ public class Solution79 {public static boolean exist(char[][] board, String word) {int row = board.length;int col = board[0].length;boolean[][] visited = new boolean[row][col];//record whether this cell is visitedfor(int i=0;i<row;i++)for(int j=0;j<col;j++)if(dfs(board,visited,i,j,0,word))// calling the function to check word return true;//if this start position(i,j) can match the word then just return truereturn false;//if all the position can't match the word then return false }private static boolean dfs(char[][] board, boolean[][] visited, int row, int col, int index, String word) {if(word.length() == index){//judge whether match the wordreturn true;}if(row<0 || col<0|| row>=board.length || col>=board[0].length) return false;//considering the boundarychar ch = word.charAt(index);//get next Characterif(!visited[row][col] && ch == board[row][col]){// this position can match the Charactervisited[row][col] = true;//calling itself going through the tree//four conditions: up && down && left && rightboolean res = dfs(board,visited,row-1,col,index+1,word)|| dfs(board,visited,row+1,col,index+1,word)||dfs(board,visited,row,col-1,index+1,word)|| dfs(board,visited,row,col+1,index+1,word);visited[row][col] = false;return res;}return false;//not found } }

 

 

 

转载于:https://www.cnblogs.com/zpfbuaa/p/6634147.html

总结

以上是生活随笔为你收集整理的LeetCode 79 Word Search（单词查找）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。