79. 單詞搜索

79. 單詞搜索

? 給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)字符串單詞 word 。如果 word 存在于網(wǎng)格中，返回 true ；否則，返回 false 。

? 單詞必須按照字母順序，通過(guò)相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

進(jìn)階： 你可以使用搜索剪枝的技術(shù)來(lái)優(yōu)化解決方案，使其在 board 更大的情況下可以更快解決問(wèn)題？

---

解題思路：回溯（深搜） + 剪枝

? 毫無(wú)疑問(wèn)這道題就是要使用深搜，或者說(shuō)是回溯，它們兩個(gè)的思想都是一樣的，從同一個(gè)起點(diǎn)出發(fā)，然后一直往更深層次去遍歷！但是因?yàn)檫@道題和那種迷宮問(wèn)題不太一樣，迷宮問(wèn)題是只有一個(gè)入口，但是這道題入口可能不是第一個(gè)元素，可能是其它的元素開(kāi)頭，所以我們必須 在主調(diào)用函數(shù)中進(jìn)行一個(gè) for 循環(huán)遍歷每個(gè)元素為入口的路徑，如果出現(xiàn)了成功的情況，則直接返回即可，反之說(shuō)明每個(gè)入口都是不成功匹配的，則直接返回一個(gè) false 即可，如下所示：

bool exist(vector<vector<char>>& board, string word) 
{for(int i = 0; i < board.size(); ++i){for(int j = 0; j < board[i].size(); ++j){if(遞歸函數(shù)的返回值 == true)return true;}}return false;
}

? 也就是說(shuō)此時(shí)需要設(shè)計(jì)一個(gè) dfs() 函數(shù)，幫助我們返回以某個(gè)元素為入口的路徑中是否存在匹配的字符串！這個(gè)通過(guò)前面的刷題量，其實(shí)并不難解決，我們可以分下面三步走：

1. 函數(shù)頭的設(shè)計(jì)：

   • 因?yàn)槲覀冃枰f歸函數(shù)返回一個(gè)布爾值，所以返回值就是 bool 類(lèi)型的！

   • 其次少不了的就是題目給的網(wǎng)格 board 以及要查找的字符串 word。

   • 然后因?yàn)槲覀冃枰喇?dāng)前遞歸函數(shù)走到了目標(biāo)字符串的哪個(gè)位置，所以需要一個(gè) index 變量來(lái)標(biāo)記！

   • 此外因?yàn)槲覀冃枰袛喈?dāng)前位置是否越界，所以需要有當(dāng)前位置在網(wǎng)格中的坐標(biāo)，所以需要 x 和 y 來(lái)表示！

     bool dfs(vector<vector<char>>& board, string& word, int index, int x, int y);
     

2. 遞歸函數(shù)出口：

   • 因?yàn)檫@道題要求說(shuō)同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用，所以我們需要一個(gè) 全局的布爾類(lèi)型二維數(shù)組 used 來(lái)標(biāo)記當(dāng)前位置是否已經(jīng)走過(guò)，這樣子往下的路徑就能知道哪些該走哪些不該走！

   • 然后主要就是判斷以下內(nèi)容：

     1. 當(dāng)前在網(wǎng)格中的坐標(biāo)是不是越界了
     2. 當(dāng)前元素是否已經(jīng)走過(guò)了
     3. 當(dāng)前元素是否為目標(biāo)字符串中對(duì)應(yīng)的字符

   • 如果出現(xiàn)其中一個(gè)不符合的話，則直接 return false 即可！

     // 遞歸函數(shù)出口
     if(x < 0 || x == board.size() || y < 0 || y == board[x].size() || used[x][y] == true || board[x][y] != word[index])return false;
     

3. 函數(shù)體的內(nèi)容：

   • 函數(shù)體要做的事情無(wú)非就是進(jìn)行處理當(dāng)前元素、遞歸、回溯操作。
     • 其中處理當(dāng)前元素對(duì)于這道題來(lái)說(shuō)就是標(biāo)記進(jìn)行當(dāng)前元素已經(jīng)走過(guò)，也就是將 used[x][y] = true 即可！
     • 遞歸操作的話，這里我們先判斷一下是否 index 已經(jīng)走完字符串，是的話說(shuō)明找到了符合要求的（因?yàn)椴环系脑诤瘮?shù)出口已經(jīng)被篩掉了，能到這里就是符合的），則直接返回正確即可；或者遞歸的子函數(shù)中也找到了字符串，那么也直接返回正確！
     • 對(duì)于回溯操作的話，只有當(dāng)上面沒(méi)找到字符串，才對(duì)當(dāng)前元素進(jìn)行恢復(fù)現(xiàn)場(chǎng)，然后返回失敗給上一層，表示當(dāng)前的路走不通，所以設(shè)置完 used[x][y] = false 之后，就直接返回錯(cuò)誤即可。

? 完整代碼如下所示：

class Solution {
private:bool used[6][6]; // 標(biāo)記當(dāng)前位置是否已經(jīng)走過(guò)
public:bool exist(vector<vector<char>>& board, string word) {for(int i = 0; i < board.size(); ++i){for(int j = 0; j < board[i].size(); ++j){if(dfs(board, word, 0, i, j))return true;}}return false;}bool dfs(vector<vector<char>>& board, string& word, int index, int x, int y){// 遞歸函數(shù)出口if(x < 0 || x == board.size() || y < 0 || y == board[x].size() || used[x][y] == true || board[x][y] != word[index])return false;used[x][y] = true; // 標(biāo)記進(jìn)行當(dāng)前元素已經(jīng)走過(guò)// 如果走完字符串，說(shuō)明找到了；或者遞歸的子函數(shù)中找到了字符串，則直接返回trueif(index == word.size() - 1 || dfs(board, word, index + 1, x + 1, y) || dfs(board, word, index + 1, x, y + 1) || dfs(board, word, index + 1, x - 1, y) || dfs(board, word, index + 1, x, y - 1))return true;// 只有當(dāng)上面沒(méi)找到字符串，才對(duì)當(dāng)前元素進(jìn)行恢復(fù)現(xiàn)場(chǎng)，然后返回失敗給上一層，表示當(dāng)前的路走不通used[x][y] = false;return false;}
};