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

0079. Word Search (Medium)

(當然，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:

1
2
3
4
5
6
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

1
2
3
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

每一次我們要做的步驟：

檢查board[r][c]和word的index處的值是否不同 ，
不同則回傳False 表示這條路行不通。
檢查index 是否已經走到最後了(length of word - 1 )，
是的話代表這條路到這邊剛好就是答案，回傳True 。
將index遞增 (接下來要給下面遞迴使用)，並將board[r][c]標明已造訪 。
分別以往上下左右 方向的新的(r, c)值來代入函式進行遞迴搜尋 ，
如果結果是True的話，直接回傳True 。(也就是下面的部份都不用做了XD)
(這邊記得要檢查上下左右移動一格以後是否超出board範圍 )
前面四個都是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學演算法，我們下次見囉，掰~