Python describe LeetCode 79. Word search

Hello everyone , I'm Qi Guanjie （qí guān jié ）, stay 【 Qi Guanjie 】 official account 、CSDN、GitHub、B Share some technical blog posts on the website and other platforms , It mainly includes front-end development 、python The backend development 、 Applet development 、 Data structure and algorithm 、docker、Linux Common operation and maintenance 、NLP And other related technical blog , Time flies , Future period , come on. ~

If you love bloggers, you can focus on the bloggers' official account. 【 Qi Guanjie 】(qí guān jié), The articles inside are more complete and updated faster . If you need to find a blogger, you can leave a message at the official account. , I will reply to the message as soon as possible .

---

This article was originally written as 【 Qi Guanjie 】（qí guān jié ）, Please support the original , Some platforms have been stealing blog articles maliciously ！！！ All articles please pay attention to WeChat official account 【 Qi Guanjie 】.

subject

Given a m x n Two dimensional character grid board And a string word word . If word Exists in the grid , return true ; otherwise , return false .

The words must be in alphabetical order , It's made up of letters in adjacent cells , among “ adjacent ” Cells are those adjacent horizontally or vertically . Letters in the same cell are not allowed to be reused .

Example 1：

 Input ：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output ：true

Example 2：

 Input ：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output ：true

Example 3：

 Input ：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output ：false

Tips ：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word It consists of upper and lower case English letters only

** Advanced ：** You can use search pruning techniques to optimize solutions , Make it board Larger situations can solve problems faster ？

Python describe

Explosive search , Each word here can only be used once , Add an access array control

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