從LeetCode學演算法 - 59 Backtracking (2) / DFS (4)

0079. Word Search (Medium)

寫在前面： 請幫我隨手點開下面的SHOW EMBED並按5個like~ (按讚不用錢，感謝支持寫作~) (當然，Medium的拍手也可以多拍幾下啦XD)

Question: Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of a sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

分析/解題： 給定一個2維棋盤和一個字(word)，檢查這個字是否存在這個棋盤裡。 構成字的方式是從棋盤的某一格開始，連續選取相鄰的格子。 同時，相同的格子不能使用兩次。

前面提到過Backtracking(回溯法)， 這題同樣也是典型的DFS+Backtracking方法可以處理的對象。

首先，要構成一個字，就要從棋盤上選擇一個位置開始往下。 每次選一個相鄰的格子，拿來跟word比對， 都必須要和word對應的位置上的字元(char)相同才行， 所以這表示我們還要記錄現在比對到哪個index了。 同時，由於用過的格子不能重複使用，每次在進入dfs的時候， 我們必須要記錄是否有造訪(visit)過這個格子， 才往更深處呼叫；同時，在該層的四個方向都判斷完以後， 回到上一層之前，必須將造訪的紀錄還原回去。 (因為我們只有在這次走這條路的時候有造訪， 回到上一層的時候這個格子應該處於沒有造訪過的狀態)

所以最開始我們要做的事情是， 使用迴圈分別將每個cell作為起始點，開始進行搜尋。 (搜尋的遞迴函式如果其中一次是True的話就可以直接回傳True)

每次搜尋的時候，傳入的有： board(棋盤), r, c(當前的cell位置), index(比對到word的哪一個char), word

每一次我們要做的步驟： 1. 檢查board[r][c]和word的index處的值是否不同， 不同則回傳False表示這條路行不通。 2. 檢查index是否已經走到最後了(length of word - 1)， 是的話代表這條路到這邊剛好就是答案，回傳True。 3. 將index遞增(接下來要給下面遞迴使用)，並將board[r][c]標明已造訪。 4. 分別以往上下左右方向的新的(r, c)值來代入函式進行遞迴搜尋， 如果結果是True的話，直接回傳True。(也就是下面的部份都不用做了XD) (這邊記得要檢查上下左右移動一格以後是否超出board範圍) 5. 前面四個都是False的狀況，代表這條路行不通了， 我們要回到上一步，這時候要先將board[r][c]標明未造訪， 才回傳False。

如果跑完整個棋盤，都沒有能夠成立的路徑的話， 就應該回傳False作為答案。(因為我們沒有找到可行的路徑)

在實作時為了方便起見，我們可以宣告class的變數來放一些常用的東西， 這邊用了wlen(word的長度), row, col(board的列/行數)。 需要注意的是，在實作造訪與否的紀錄時， 我們可以選擇使用像是visited[][]的二維陣列來寫， 但也可以採用別的方法，比如將裡面的值暫時設為"0"， 後面再還原，或者像Java這邊寫的將其和128進行XOR。

為什麼和128進行XOR呢？ 因為ASCII中的所有字元值均不超過128， 也就是說，它們在二進位上的第8位數(由右數到左)均為0。 XOR後，第8位數會變成1，所以再度遞迴下去比對時， 就不可能等於任何字元，從而達到標示造訪過的目的。

還原回來的時候，因為： a XOR 128 XOR 128 ＝ a XOR 0 = a (先前的文章有提到過的Bitwise Operation)

所以再重複用128進行一次XOR即可還原原先的值了！

寫成程式碼如下： (留意Java可以直接對char當作是數字來操作)

Java:

Python:

面試實際可能會遇到的問題： 「時間/空間複雜度？」 (如果row = m, col = n，word長度=l的話，從每個點出發一次， 並且每次都有4個方向的選擇(但只有三個方向能繼續延伸)， 時間複雜度會是O(m * n * 3^L)。 空間複雜度的部分，如果考慮call stack的話，最大會是O(L)， 不考慮的話，由於沒有使用visited[][]來處理，則會是O(1)。 如果用visited來存放的話則是O(m*n))

「在Python中是否可以使用類似Java對char的解法來處理呢？」 (可以，請使用ord()將單個字元進行轉換成數字再進行xor， 不能直接用str型態的値來處理。)

相似及延伸： Special Thanks suggestions/corrections from viewers: Raiy Kuo: 細算的話選擇方向這部份的時間複雜度是3^L， 詳情請見response中的討論。

(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

如果你／妳覺得這篇文章不錯，請給我5個拍手，並且給我5個Like。(點開SHOW EMBED!)
如果你／妳非常喜歡這篇文章，可以按著拍手直到50下。
也請記得「Follow」我，隨時收看最新的文章。