題目鏈接:https://leetcode.com/problems/word-search/#/description

?

給出一個(gè)二維字符表，并給出一個(gè)String類型的單詞，查找該單詞是否出現(xiàn)在該二維字符表中。

?

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題的方法，也就是回溯法求解。

通過上述例子，每次都是只能查找當(dāng)前位置的上下左右四個(gè)位置（最多是四個(gè)位置，還有邊界情況）。當(dāng)查找到該單詞的某個(gè)位置時(shí)，通過計(jì)數(shù)器不斷更新當(dāng)前已經(jīng)匹配的字符的個(gè)數(shù)。

通過移動(dòng)查找的坐標(biāo)(row,col)來進(jìn)行對(duì)一棵樹的深度遍歷操作。也就是dfs遍歷操作。

調(diào)用dfs遍歷的循環(huán)是有兩層的。每次當(dāng)遍歷的一棵子樹到葉子節(jié)點(diǎn)時(shí)，重新進(jìn)入原始的循環(huán)體。更新樹的遍歷根節(jié)點(diǎn)。

因此循環(huán)體為

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

?

需要考慮遞歸函數(shù)的出口問題：因?yàn)樾枰獙?duì)單詞中的每個(gè)字符進(jìn)行匹配操作，所以設(shè)置計(jì)數(shù)器用來統(tǒng)計(jì)當(dāng)前所匹配的字符個(gè)數(shù)，同時(shí)也可以使用該變量來得到接下來要匹配的單詞的字符。

如果給計(jì)數(shù)器個(gè)數(shù)等于單詞的長(zhǎng)度時(shí)，說明單詞的所有字符都可以在表中找到，此時(shí)返回結(jié)果為true

如果當(dāng)前的位置上下左右四個(gè)cell都不能與單詞的字符進(jìn)行匹配時(shí)，此時(shí)遞歸函數(shù)應(yīng)退出并放回結(jié)果為false;

?

?

上面考慮了遞歸函數(shù)的出口問題，下面是對(duì)整個(gè)問題的結(jié)果進(jìn)行討論。

當(dāng)有一個(gè)位置能夠查找到目標(biāo)單詞的所有字符時(shí)就應(yīng)該返回true，

當(dāng)遍歷開始位置從(0,0)到(board.row, board.col)結(jié)束都沒有查找到時(shí)，返回false；

?

根據(jù)上述分析，得到以下參考代碼：

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 } }

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/zpfbuaa/p/6634147.html

總結(jié)

以上是生活随笔為你收集整理的LeetCode 79 Word Search（单词查找）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。