文章目錄

• 單詞搜索
• • DFS ：
  • 小小的優化
• 總結

---

單詞搜索

??????題目鏈接：https://leetcode-cn.com/problems/word-search/

??????題目描述：
給定一個 m x n 二維字符網格 board 和一個字符串單詞 word 。如果 word 存在于網格中，返回 true ；否則，返回 false 。

單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重復使用。

DFS ：

??????算法1：對每一個可能的點采用DFS遍歷，判斷是否可以得到唯一解，若存在即返回true，否則為 false。其中在遞歸過程中，flag 數組的值需要在遞歸之前置為 true，遞歸之后置為 flase，即它的狀態需要回退。參考代碼如下（帶注釋）：

int[] addi={1,-1,0,0};int[] addj={0,0,1,-1};boolean[][] flag;public boolean exist(char[][] board, String word) {int m=board.length,n=board[0].length;flag=new boolean[m][n];//flag數組用來標記某個字符是否被訪問過for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j]==word.charAt(0)){//對每一個首字符都需要進行DFS遍歷，判斷是否在此處可以搜索到到完整的字符串if(solve(board,i,j,word,1))return true;}}}return false;}/*想一想，在每次調用 slove 方法時，flag 數組的所有值應該都為 false 吧，即上一次 solve 方法對 flag 造成的影響和下一次 solve 方法調用 flag 無關， flag 的功能僅是為了在一次遍歷中不要重復訪問已訪問過的字符。一次不成功的搜索之后，訪問過的元素（flag 值為 true）應該需要再次置為 false。在下一次搜索時應該還可以訪問這些元素，也就是說，flag 數組的值有一個回退的動作，*/boolean solve(char[][] board,int i,int j,String word,int count){if(count==word.length())//退出條件return true;flag[i][j]=true; //flag 中的當前元素以訪問，置為 trueboolean re=false;//保存退出返回值for(int k=0;k<4;k++){int newI=i+addi[k],newJ=j+addj[k];if(newI<0||newJ<0||newI>=board.length||newJ>=board[0].length||flag[newI][newJ]==true)continue;if(board[newI][newJ]==word.charAt(count))//一種可能成功的情況re=re||solve(board,newI,newJ,word,count+1);//這里為或操作}flag[i][j]=false; //flag 重新恢復為falsereturn re;}

??????算法2：另外一種描述方法如下（添加一個 boolean 變量 ans 來判斷是否搜索到字符串）：

int[] addi={1,-1,0,0};int[] addj={0,0,1,-1};boolean[][] flag;boolean ans;public boolean exist(char[][] board, String word) {int m=board.length,n=board[0].length;flag=new boolean[m][n];for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j]==word.charAt(0)){solve(board,i,j,word,1);if(ans==true)return true;}}}return false;}void solve(char[][] board,int i,int j,String word,int count){if(count==word.length()){ans=true;return;}flag[i][j]=true;for(int k=0;k<4;k++){int newI=i+addi[k],newJ=j+addj[k];if(newI<0||newJ<0||newI>=board.length||newJ>=board[0].length||flag[newI][newJ]==true)continue;if(board[newI][newJ]==word.charAt(count))solve(board,newI,newJ,word,count+1);}flag[i][j]=false;}

小小的優化

??????算法1 和 2 都還需要優化，它們都有同一個問題，在搜索到字符串之后不會立即返回，這樣會浪費時間的。算法1 改進如下：

for(int k=0;k<4;k++){int newI=i+addi[k],newJ=j+addj[k];if(newI<0||newJ<0||newI>=board.length||newJ>=board[0].length||flag[newI][newJ]==true)continue;if(board[newI][newJ]==word.charAt(count)){re=re||solve(board,newI,newJ,word,count+1);if(re)break;}}

??????一旦搜索到字符串之后，此時re 為 true，短路 || 不會執行 solve(board,newI,newJ,word,count+1) ,但是也應該加上 break 語句讓程序執行跳出 for 循環，直接退出返回正確的結果。相應的也可對算法 2 進行優化。

總結

??????深度優先遍歷是回溯算法使用的策略。

總結

以上是生活随笔為你收集整理的LeetCode算法题13：DFS/BFS - 单词搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。