LeetCode 刷题记录: 79. Word Search [Python]

原题

https://leetcode.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 cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

思路

DFS。四个方向搜寻即可。

代码

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board: return False
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfs(board,i,j,word): return True
        return False
    def dfs(self, board, i, j, word):
        if len(word)==0: return True
        if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or word[0]!=board[i][j]: return False
        tmp,board[i][j]=board[i][j],'#'
        res=self.dfs(board,i-1,j,word[1:]) or self.dfs(board,i+1,j,word[1:]) or self.dfs(board,i,j-1,word[1:]) or self.dfs(board, i, j+1, word[1:])
        board[i][j]=tmp
        return res

# DFS, LeetCode

支付宝

微信

Paypal Buy me a coffee

LeetCode 刷题记录: 79. Word Search [Python]

原题

思路

代码

喜欢这篇文章？打赏一下作者吧

评论

分类

标签

最新文章

归档

最新文章

归档

Your browser is out-of-date!