題目

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

例如，在下面的 3×4 的矩陣中包含單詞 "ABCCED"（單詞中的字母已標出）。

示例 1：

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

示例 2：

輸入：board = [["a","b"],["c","d"]], word = "abcd"
輸出：false

提示：

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

解題思路

1.題目要求我們查詢所給的字符串是否在矩陣中，我們采用深度優先遍歷算法去求解此題。

2.舉個例子：word = ABCCED

按照右下左上的順序開始尋找，在這個時候我們需要設置一個用于記錄的二維數組visited，將訪問過的元素在visited數組中的相同的下標處置為true。

我們首先從左上角的A開始尋找，發現A與word中的第一個元素A是相等的，那么我們就將Visited[0][0]設置為true

?

?然后我們按照順序向右進行搜索，發現B與word中的第二個元素B是相等的

?

再次向右進行搜索

??

繼續向右，這個時候我們發現E與word中的第四個元素不同了，那么我們就要進行回溯，退回元素C。

然后再向下進行搜索

??

?S與word中的第五個元素不同，進行回溯

?

E與word中的第六個元素不同，進行回溯，當我們向下搜索時發現數組越界了，這時候我們就按搜索順序向左進行搜索。

我們成功找到了目標字符串。

?3.代碼思路，使用深度優先搜索（DFS）的方式，在board中尋找與word相匹配的字符。

如果當前字符與word的第一個字符不匹配，返回false。如果當前字符與word的最后一個字符匹配，說明已經找到了一個匹配的單詞，返回true。標記當前字符為已訪問，然后遞歸搜索當前字符的相鄰字符。如果相鄰字符中有一個能匹配word的下一個字符，返回true。如果相鄰字符都不能匹配word的下一個字符，返回false。回溯，將當前字符標記為未訪問。遍歷完board中的所有字符都沒有找到匹配的單詞，返回false。

代碼實現

class Solution {int n;int m;int len;boolean [][] visited;public boolean exist(char[][] board, String word) {this.n = board.length;this.m = board[0].length;this.len = word.length();visited = new boolean[n][m];for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(dsf(board, i, j, word, 0)){return true;}}}return false;}public boolean dsf(char[][] board, int i, int j, String word, int k){if(i<0 || i>=n || j<0 || j>=m || visited[i][j] || board[i][j] != word.charAt(k)){return false;}if(k == len - 1){return true;}visited[i][j] = true;boolean res = dsf(board, i, j + 1, word, k + 1)||dsf(board, i + 1, j, word, k + 1)||dsf(board, i, j - 1, word, k + 1)||dsf(board, i - 1, j, word, k + 1);visited[i][j] = false;return res;}
}

測試結果

?