LeetCode-79 單詞搜尋☆中等，偏移量技巧
題目：給定一個二維網格和一個單詞，找出該單詞是否存在於網格中。
單詞必須按照字母順序，透過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重複使用。
示例：
board =
［
［‘A’，‘B’，‘C’，‘E’］，
［‘S’，‘F’，‘C’，‘S’］，
［‘A’，‘D’，‘E’，‘E’］
］
給定 word = “ABCCED”， 返回 true。
給定 word = “SEE”， 返回 true。
給定 word = “ABCB”， 返回 false。
思路：這題想到要用遞迴，但難點在於下一層遞迴的四個方向的座標計算、狀態的重置、以及如何回溯、如何判斷是否找到這4個條件。
#這是自己第一遍寫得程式碼，存在很多冗餘，比如遞迴結束的條件、formed的使用、上下左右的座標計算方法、
#狀態重置的寫法等，最後執行超時
class
Solution
：
def
exist
（
self
，
board
：
List
［
List
［
str
］］，
word
：
str
）
->
bool
：
row
=
len
（
board
）
if
row
==
0
：
return
False
column
=
len
（
board
［
0
］）
if
column
==
0
：
return
False
l_word
=
len
（
word
）
if
l_word
==
0
or
l_word
>
row
*
column
：
return
False
used
=
［［
0
for
j
in
range
（
column
）］
for
i
in
range
（
row
）］
start
=
［］
#先找到可以匹配的起點
for
i
in
range
（
row
）：
for
j
in
range
（
column
）：
if
board
［
i
］［
j
］
==
word
［
0
］：
start
。
append
（［
i
，
j
］）
def
search
（
start
，
formed
，
word
，
l
，
used
，
res
）：
# flag = False
if
len
（
formed
［：］）
==
l
：
# print（formed）
res
。
append
（
formed
）
return
if
len
（
word
）
==
0
：
return
around_first
=
［［
max
（
start
［
0
］
-
1
，
0
），
start
［
1
］］，
［
start
［
0
］，
min
（
start
［
1
］
+
1
，
column
-
1
）］，
［
min
（
start
［
0
］
+
1
，
row
-
1
），
start
［
1
］］，
［
start
［
0
］，
max
（
start
［
1
］
-
1
，
0
）］］
#上、右、下、左
around_first
=
［
item
for
item
in
around_first
if
item
！=
start
and
not
used
［
item
［
0
］］［
item
［
1
］］］
for
i
in
around_first
：
# print（i）
if
board
［
i
［
0
］］［
i
［
1
］］
==
word
［
0
］：
used
［
i
［
0
］］［
i
［
1
］］
=
1
formed
。
append
（
word
［
0
］）
search
（
i
，
formed
，
word
［
1
：］，
l
，
used
，
res
）
# if search（i， formed， word［1：］， l， used， flag）：flag = True
formed
。
pop
（）
used
［
start
［
0
］］［
start
［
1
］］
=
0
res
=
［］
for
first
in
start
：
formed
=
［
word
［
0
］］
used
［
first
［
0
］］［
first
［
1
］］
=
1
search
（
first
，
formed
，
word
［
1
：］，
l_word
，
used
，
res
）
if
len
（
res
）
>
0
：
return
True
#判斷是否成功的條件太麻煩
used
=
［［
0
for
j
in
range
（
column
）］
for
i
in
range
（
row
）］
#該步完全多餘
return
False
對比liweiwei1419的如下程式碼：
from
typing
import
List
class
Solution
：
# （x-1，y）
# （x，y-1） （x，y） （x，y+1）
# （x+1，y）
directions
=
［（
0
，
-
1
），
（
-
1
，
0
），
（
0
，
1
），
（
1
，
0
）］
def
exist
（
self
，
board
：
List
［
List
［
str
］］，
word
：
str
）
->
bool
：
m
=
len
（
board
）
if
m
==
0
：
return
False
n
=
len
（
board
［
0
］）
marked
=
［［
False
for
_
in
range
（
n
）］
for
_
in
range
（
m
）］
for
i
in
range
（
m
）：
for
j
in
range
（
n
）：
# 對每一個格子都從頭開始搜尋
if
self
。
__search_word
（
board
，
word
，
0
，
i
，
j
，
marked
，
m
，
n
）：
return
True
return
False
def
__search_word
（
self
，
board
，
word
，
index
，
start_x
，
start_y
，
marked
，
m
，
n
）：
# 先寫遞迴終止條件
if
index
==
len
（
word
）
-
1
：
return
board
［
start_x
］［
start_y
］
==
word
［
index
］
# 中間匹配了，再繼續搜尋
if
board
［
start_x
］［
start_y
］
==
word
［
index
］：
# 先佔住這個位置，搜尋不成功的話，要釋放掉
marked
［
start_x
］［
start_y
］
=
True
for
direction
in
self
。
directions
：
new_x
=
start_x
+
direction
［
0
］
new_y
=
start_y
+
direction
［
1
］
# 注意：如果這一次 search word 成功的話，就返回
if
0
<=
new_x
<
m
and
0
<=
new_y
<
n
and
\
not
marked
［
new_x
］［
new_y
］
and
\
self
。
__search_word
（
board
，
word
，
index
+
1
，
new_x
，
new_y
，
marked
，
m
，
n
）：
return
True
marked
［
start_x
］［
start_y
］
=
False
return
False
將自己的程式碼修改之後：
class
Solution
：
def
exist
（
self
，
board
：
List
［
List
［
str
］］，
word
：
str
）
->
bool
：
row
=
len
（
board
）
if
row
==
0
：
return
False
column
=
len
（
board
［
0
］）
if
column
==
0
：
return
False
used
=
［［
0
for
j
in
range
（
column
）］
for
i
in
range
（
row
）］
def
search
（
start
，
word
，
board
，
used
）：
#偏移量陣列，在二維平面內經常使用的技巧
directions
=
［（
-
1
，
0
），（
0
，
1
），（
1
，
0
），（
0
，
-
1
）］
#終止條件寫成這樣是避免Word中僅有一個字元
if
len
（
word
）
==
1
：
return
board
［
start
［
0
］］［
start
［
1
］］
==
word
［
0
］
if
board
［
start
［
0
］］［
start
［
1
］］
==
word
［
0
］：
used
［
start
［
0
］］［
start
［
1
］］
=
1
for
i
in
directions
：
new_x
=
start
［
0
］
+
i
［
0
］
new_y
=
start
［
1
］
+
i
［
1
］
#此處的遞迴形式寫得很好，將遞迴作為條件之一，得到返回
if
0
<=
new_x
<
row
and
0
<=
new_y
<
column
and
not
used
［
new_x
］［
new_y
］
and
\
search
（（
new_x
，
new_y
），
word
［
1
：］，
board
，
used
）：
return
True
#狀態重置，如果沒有下一匹配的字元，將釋放當前的字元佔用，即為回溯
used
［
start
［
0
］］［
start
［
1
］］
=
0
return
False
for
i
in
range
（
row
）：
for
j
in
range
（
column
）：
if
search
（（
i
，
j
），
word
，
board
，
used
）：
return
True
return
False
已經戰勝
73。85
%
的
python3
提交記錄
作者的程式碼直接
暴力遍歷，就開始匹配
。
比如：先找出可以匹配的起點位置。可以提升一點T（O）
說明：
1、偏移量陣列在二維平面內是經常使用的，可以把它的設定當做一個技巧，並且在這個問題中，偏移量陣列內的 4 個偏移的順序無關緊要；
說明：類似使用這個技巧的問題還有：
「力扣」第 130 題：被圍繞的區域
、
「力扣」第 200 題：島嶼數量
2、對於這種搜尋演算法，我認為理解 DFS 和狀態重置並不難，程式碼編寫也相對固定，難在程式碼的編寫和細節的處理，建議多次編寫，自己多總結多思考，把自己遇到的坑記下。