字母從任意位置出發(fā)移動，不能重復(fù)移動，若能構(gòu)成單詞，則true，否則返回false。示例：

給定map=[[a d c],

? ? ? ? ?[f? e? d],

? ? ? ? ?[g n m]

]; 若string為fedc則true；若gnme則false。

解題思想：以每一個字母為出發(fā)點，向四周遍歷，若不符合單詞，則返回false，否則繼續(xù)遍歷，直到達到單詞長度，則返回true。

先建立一個字母檢測函數(shù)，再對數(shù)組中的每一個字母進行檢測，若通過則直接返回true

檢測函數(shù)需要告訴我們這個字母為起點是否可以搜索到單詞，故為bool類型，不可以走回頭路，所有需要建立一個等大小二維數(shù)組記錄移動過的位置，若遍歷至該位置，則直接跳出。

以下為代碼分析：

遍歷函數(shù)：

?bool exist(vector<vector<char>>& board, string word) {? 輸入?yún)?shù)為字母數(shù)組和目標單詞

? ? ? ? int h = board.size(), w = board[0].size();? ? ? ? ? ? ? ? ? ? ?h為二維數(shù)組的行數(shù)，w為列數(shù)

? ? ? ? vector<vector<int>> visited(h, vector<int>(w));??建立一個等大的visited矩陣，防止重復(fù)

? ? ? ? for (int i = 0; i < h; i++) {? ? ?

? ? ? ? ? ? for (int j = 0; j < w; j++) {? ? ? ? ? ? ? ? ? ? 2重循環(huán)遍歷數(shù)組每個元素

? ? ? ? ? ? ? ? bool flag = check(board, visited, i, j, word, 0); 傳入兩個二維數(shù)組，當前字母坐標? ? ?

? ? ? ? ? ? ? ? if (flag) {

? ? ? ? ? ? ? ? ? ? return true;? ? ? ? 如果在某次遍歷中獲得了true的結(jié)果，則word被找到，返回true

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return false;? ? ?如果遍歷完所有字母仍未找到，則意味著沒有，返回false

? ? }

字母檢測函數(shù)：

?bool check(vector<vector<char>>& board, vector<vector<int>>& visited, int i, int j, string& s, int k) {? ? ? k為單詞字符串下標，用來索引單詞字母

? ? ? ? if (board[i][j] != s[k]) {? ??

? ? ? ? ? ? return false;? ? ? 如果首字母都對不上，直接false，去查下一個字母起點

? ? ? ? } else if (k == s.length() - 1) {

? ? ? ? ? ? return true;? ? ?校對完了單詞的所有字母都有對應(yīng)，則單詞被找到，返回true

? ? ? ? }

? ? ? ? visited[i][j] = true;? ?重置參數(shù)，當前字母位置被拜訪，標記為true

? ? ? ? vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 可以對上下左右查找

? ? ? ? bool result = false;? 重置參數(shù)，查找結(jié)果默認為沒找到

? ? ? ? for (const auto& dir: directions) {? 對4個方向分別進行查找

? ? ? ? ? ? int newi = i + dir.first, newj = j + dir.second; 更新查找坐標，進行“移動”

? ? ? ? ? ? if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size())確認新的移動到的位置沒有越界，若越界則重新進行移動

{

? ? ? ? ? ? ? ? if (!visited[newi][newj]) {?

? ? ? ? ? ? ? ? ? ? bool flag = check(board, visited, newi, newj, s, k + 1);??若移動到的新位置被拜訪過，則直接跳過，重新移動。若移動到的新位置沒被拜訪過，則進行迭代，單詞下標索引加1，以這個新位置為首字母繼續(xù)向下檢測，若返回錯誤，則返回循環(huán)，繼續(xù)移動剩下的次數(shù)，若都錯誤，則該字母查找失敗，給該字母ij重置為未拜訪，以下一個字母為起點進行新的一輪查找。若返回正確，則意味著找出整個單詞，跳出那層函數(shù)并賦值給flag，跳出循環(huán)，返回true，進而讓遍歷函數(shù)知道這個首字母找到了完整單詞，返回為真，任務(wù)結(jié)束。（核心）

? ? ? ? ? ? ? ? ? ? if (flag) {

? ? ? ? ? ? ? ? ? ? ? ? result = true;? flag為

? ? ? ? ? ? ? ? ? ? ? ? break;

? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? visited[i][j] = false;

? ? ? ? return result;

? ? }

代碼最好結(jié)合著實例一起看，會比較容易理解。

源碼鏈接：https://leetcode.cn/problems/word-search/solution/dan-ci-sou-suo-by-leetcode-solution/