?LeetCode刷題實(shí)戰(zhàn)79：?jiǎn)卧~搜索
算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問(wèn)題叫做?單詞搜索，我們先來(lái)看題面：
https://leetcode-cn.com/problems/word-search/
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
題意
board?=
[
??['A','B','C','E'],
??['S','F','C','S'],
??['A','D','E','E']
]
給定 word = "ABCCED", 返回 true
給定 word = "SEE", 返回 true
給定 word = "ABCB", 返回 false
解題
題解
class?Solution:
????def?exist(self, board: List[List[str]], word: str)?-> bool:
????????fx = [[0, 1], [0, -1], [1, 0], [-1, 0]]
????????def?dfs(x, y, l):
????????????if?l == len(word):
????????????????return?True
????????????for?i in?range(4):
????????????????nx = x + fx[i][0]
????????????????ny = y + fx[i][1]
????????????????# 出界或者是走過(guò)的時(shí)候，跳過(guò)
????????????????if?nx < 0?or?nx == n or?ny < 0?or?ny == m or?visited[nx][ny]:
????????????????????continue
????????????????if?board[nx][ny] == word[l]:
????????????????????visited[nx][ny] = 1
????????????????????if?dfs(nx, ny, l+1):
????????????????????????return?True
????????????????????visited[nx][ny] = 0
????????????return?False
????????????????
????????n = len(board)
????????if?n == 0:
????????????return?False
????????m = len(board[0])
????????if?m == 0:
????????????return?False
????????
????????visited = [[0?for?i in?range(m)] for?j in?range(n)]
????????
????????for?i in?range(n):
????????????for?j in?range(m):
????????????????# 找到合法的起點(diǎn)
????????????????if?board[i][j] == word[0]:
????????????????????visited = [[0?for?_ in?range(m)] for?_ in?range(n)]
????????????????????visited[i][j] = 1
????????????????????if?dfs(i, j, 1):
????????????????????????return?True
????????????????????
????????return?False
總結(jié)
上期推文：