专栏首页Petrichor的专栏leetcode: 79. Word Search

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.

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

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

    JNingWei
  • 虚拟机操作

    JNingWei
  • 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' 最终...

    前端小书童
  • 前端开发工具 vscode 使用技巧篇:控制台由powershell切换为cmd方法,windows下新旧版控制台cmd与powershell互切方法

    小蓝枣
  • leetcode: 37. Sudoku Solver

    …and its solution numbers marked in red.

    JNingWei
  • python 五子棋-文字版(上)

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

    用户7054460
  • Swift 有效的数独 - LeetCode

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

    韦弦zhy
  • python 实现 2048 游戏 (二)

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

    用户2870857

扫码关注云+社区

领取腾讯云代金券