# leetcode: 79. Word Search

## Python

```# 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 cell,
# where "adjacent" cells are those horizontally or vertically neighboring.
# The same letter cell may not be used more than once.
#
# For example,
# Given board =
# [
#   ['A','B','C','E'],
#   ['S','F','C','S'],
#   ['A','D','E','E']
# ]
#
# word = "ABCCED", -> returns true,
# word = "SEE", -> returns true,
# word = "ABCB", -> returns false.```

## AC

```class Solution():
def exist(self, board, word):
visited = [[False for __ in range(len(board[0]))] for _ in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
if self.existRecu(board, word, 0, i, j, visited):
return True
return False

def existRecu(self, board, word, cur, i, j, visited):
if cur == len(word):
return True
if not (0 <= i < len(board) and 0 <= j < len(board[0])) or not (not visited[i][j] and board[i][j] == word[cur]):
return False
visited[i][j] = True
res = self.existRecu(board, word, cur + 1, i + 1, j, visited) or \
self.existRecu(board, word, cur + 1, i - 1, j, visited) or \
self.existRecu(board, word, cur + 1, i, j + 1, visited) or \
self.existRecu(board, word, cur + 1, i, j - 1, visited)
visited[i][j] = False
return res

if __name__ == "__main__":
board = [
"ABCE",
"SFCS",
"ADEE"
]
assert Solution().exist(board, "ABCCED") == True
assert Solution().exist(board, "SFCS") == True
assert Solution().exist(board, "ABCB") == False```

0 条评论

• ### leetcode: 37. Sudoku Solver

…and its solution numbers marked in red.

• ### 深度学习: marginal cost (边际成本)

在看 Faster R-CNN 论文的时候看到 marginal cost (边际成本) 一词，上网一搜，居然没有人解释过该词在深度学习研究领域的定义。

• ### LeetCode <bt>79&212 Word Search I&II

Given a 2D board and a word, find if the word exists in the grid.

• ### 一天一大 lee(被围绕的区域)难度:中等-Day20200811

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终...

• ### leetcode: 37. Sudoku Solver

…and its solution numbers marked in red.

• ### python 五子棋-文字版（上）

五子棋游戏相信大家应该都非常熟悉了，作为策略型棋类游戏还是非常经典的，双方分别使用黑白两色的棋子，下在棋盘直线与横线的交叉点上，先形成五子连线者获胜；

• ### Swift 有效的数独 - LeetCode

判断一个数独是否有效，根据：Sudoku Puzzles - The Rules。 (数独规则： 每一行不能有重复的数字；每一列不能有重复的数字；将数独框划分...

• ### python 实现 2048 游戏 （二）

上一篇文章中，我们梳理了实现简易版 2048 游戏的基本知识，这篇文章将介绍如何实现各个模块。换句话说，上一次我们确定了旅行的目的地，这一次就让我们自由畅行在山...