หาว่าคำ (word) มีอยู่ใน grid 2D หรือไม่ โดยเดินได้เฉพาะขึ้น/ลง/ซ้าย/ขวา ไม่ใช้เซลล์เดิมซ้ำ
ตัวอย่าง
Board: A B C E S F C S A D E E Word: "SEE" → True Word: "ABCB" → False
อัลกอริทึม: DFS + Backtracking
- วนทุกเซลล์เป็นจุดเริ่มต้น
- DFS recursive: เช็ค bounds, ตรงตัวอักษร, mark visited (ตั้งค่าเป็น '#')
- เรียก 4 ทิศทาง index+1
- Backtrack: คืนค่าเดิม
โค้ด
class Solution:
def exist(self, board, word):
if not board or not board[0]:
return False
rows, cols = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word):
return True
if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != word[i]:
return False
temp = board[r][c]
board[r][c] = '#' # mark visited
# 4 directions
if (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or
dfs(r, c+1, i+1) or dfs(r, c-1, i+1)):
board[r][c] = temp
return True
board[r][c] = temp
return False
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return False
# ทดสอบ
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
sol = Solution()
print(sol.exist(board, "SEE")) # True
print(sol.exist(board, "ABCB")) # False
ความซับซ้อน
- Time: O(m × n × 4^L) โดย L = ความยาว word (worst case)
- Space: O(L) recursion stack
สรุป
DFS backtracking มาตรฐานสำหรับ grid search ปรับได้สำหรับ Word Search II (หลายคำ) ด้วย Trie
