Python描述 LeetCode 79. 單詞搜索

大家好，我是亓官劼（qí guān jié ），在【亓官劼】公眾號、CSDN、GitHub、B站等平台分享一些技術博文，主要包括前端開發、python後端開發、小程序開發、數據結構與算法、docker、Linux常用運維、NLP等相關技術博文，時光荏苒，未來可期，加油~

如果喜歡博主的文章可以關注博主的個人公眾號【亓官劼】(qí guān jié)，裡面的文章更全更新更快。如果有需要找博主的話可以在公眾號後台留言，我會盡快回復消息.

---

本文原創為【亓官劼】（qí guān jié ），請大家支持原創，部分平台一直在惡意盜取博主的文章！！！ 全部文章請關注微信公眾號【亓官劼】。

題目

給定一個 m x n 二維字符網格 board 和一個字符串單詞 word 。如果 word 存在於網格中，返回 true ；否則，返回 false 。

單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重復使用。

示例 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 僅由大小寫英文字母組成

**進階：**你可以使用搜索剪枝的技術來優化解決方案，使其在 board 更大的情況下可以更快解決問題？

Python描述

爆搜，這裡每個單詞只能用一次，加一個訪問數組控制

class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
res = False
n,m,lw = len(board),len(board[0]),len(word)
dr = [[-1,0],[0,1],[1,0],[0,-1]]
v = [[0 for _ in range(m)] for __ in range(n)]
def dfs(dx,dy,pos):
nonlocal res,lw,word
if pos == lw:
res = True
return
for d in range(4):
nx,ny = dx+dr[d][0], dy+dr[d][1]
if 0 <= nx < n and 0 <= ny < m and v[nx][ny] == 0 and board[nx][ny] == word[pos]:
v[nx][ny] = 1
dfs(nx,ny,pos+1)
v[nx][ny] = 0
for i in range(n):
for j in range(m):
if board[i][j] == word[0]:
v[i][j] = 1
dfs(i,j,1)
if res:
return res
v[i][j] = 0
return False