單詞搜索

給出一個二維字符數組和一個單詞，判斷單詞是否在數組中出現，

單詞由相鄰單元格的字母連接而成，相鄰單元指的是上下左右相鄰。同一單元格的字母不能多次使用。

數據范圍：

0 < 行長度 <= 100

0 < 列長度 <= 100

0 < 單詞長度 <= 1000

回溯/深搜

深度優先搜索，我們定義這樣一種搜索順序，即先枚舉單詞的起點，然后依次枚舉單詞的每個字母。在這個過程中需要將已經使用過的字母改成一個特殊字母，以避免重復使用字符。

在主函數中兩層循環遍歷整個二維數組,找出所有滿足等于單詞第一個字符的,然后創建一個深搜函數,把這個節點的下標.以及第幾個字母傳入dfs函數,這個函數用于判斷單詞是否在二維數組中.

dfs函數的函數頭:boolean dfs(String[] board, int i, int j, int pos)

//pos是記錄搜索到哪個字母了

函數體:從傳入的結點開始向四周搜索(可以借助偏移數組)

同時,對搜索過的坐標進行標記,避免重復搜索

如果滿足不越界,沒判斷過且等于對應單詞字符,就遞歸下一個

所有都滿足就返回true,反之返回false

結束條件:搜索到單詞的最后一個字符

注意:可以將一些函數中用到的數據定義為全局變量,減少參數傳遞

時間復雜度:單詞起點一共有 n2個，單詞的每個字母一共有上下左右四個方向可以選擇，但由于不能走回頭路，所以除了單詞首字母外，僅有三種選擇。所以總時間復雜度是 O(n2·3k)。?

代碼:

import java.util.*;
public class Solution {int m, n;int[] dx = {0, 0, 1, -1};//偏移數組int[] dy = {1, -1, 0, 0};char[] word = {};boolean[][] ans;//用于標記是否已經搜索public boolean exist (String[] board, String _word) {word = _word.toCharArray();m = board.length;n = board[0].length();ans = new boolean[m][n];for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(word[0] == board[i].charAt(j)) {//遍歷所有字母if(dfs(board, i, j, 0) == true) return true;}}}return false;}public boolean dfs(String[] board, int i, int j, int pos) {if(pos == word.length-1) {//pos是記錄搜索到哪個字母了return true;}ans[i][j] = true;//標記以搜索for(int a = 0; a < 4; a++) {//上下左右搜索int x = i + dx[a];int y = j + dy[a];if(x < m && x >= 0 && y < n && y >= 0 && !ans[x][y] && board[x].charAt(y) == word[pos+1]) {//沒搜索過且字母相等if(dfs(board, x, y, pos+1)) return true;}}ans[i][j] = false;//走到這里說沒搜到,更改標記為未搜return false;}
}