资讯专栏INFORMATION COLUMN

【Leetcode】79.单词搜索

Caicloud / 1338人阅读

摘要:题目给定一个二维网格和一个单词,找出该单词是否存在于网格中。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中相邻单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

题目

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

题解

这个题目拿到题目就应该能想到是用DFS的题目,因为这完完全全就是DFS,没有做任何的变形,关于DFS,这里就不重复讲解。

推荐一个b站上的视频,不熟悉的同学可以回顾一下。

https://www.bilibili.com/vide...

熟悉的同学直接看代码吧

java
class Solution {
    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0) {
            return true;
        }
        char[] chs = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, chs, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, char[] words, int index, int x, int y) {
        if (index == words.length) {
            return true;
        }
        if (x < 0 || x == board.length || y < 0 || y == board[0].length) {
            return false;
        }
        if (board[x][y] != words[index]) {
            return false;
        }
        char source = board[x][y];
        board[x][y] = "";
        boolean exist = dfs(board, words, index + 1, x, y + 1)
                || dfs(board, words, index + 1, x, y - 1)
                || dfs(board, words, index + 1, x + 1, y)
                || dfs(board, words, index + 1, x - 1, y);
        board[x][y] = source;
        return exist;
    }
}
python
class Solution:
    def dfs(self, board, word, index, x, y):
        if not board or index == len(word):
            return True
        if x < 0 or x == len(board) or y < 0 or y == len(board[0]):
            return False
        if board[x][y] != word[index]:
            return False
        source = board[x][y]
        board[x][y] = ""
        exist = self.dfs(board, word, index + 1, x, y + 1) or self.dfs(board, word, index + 1, x, y - 1) or self.dfs(
            board, word, index + 1, x + 1, y) or self.dfs(board, word, index + 1, x - 1, y)
        board[x][y] = source
        return exist

    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if len(word) == 0:
            return False
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfs(board, word, 0, i, j):
                    return True
        return False
热门阅读

MySQL索引背后的数据结构及算法原理

【Leetcode】78. 子集

【Leetcode】77. 组合

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/77321.html

相关文章

  • Leetcode79.单词搜索

    摘要:题目给定一个二维网格和一个单词,找出该单词是否存在于网格中。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中相邻单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 题目 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中相邻单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允...

    ruicbAndroid 评论0 收藏0
  • 6-9月技术文章汇总

    摘要:分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥?...

    miya 评论0 收藏0
  • Leetcode】82. 删除排序链表中的重复元素 II

    摘要:题目给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中没有重复出现的数字。示例输入输出示例输入输出题解在所有题目中,我觉得链表题目是最简单的。具体画图模拟一道题就可以了。 题目 给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。 示例 1: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示例 2: 输入: 1->...

    kelvinlee 评论0 收藏0
  • Leetcode】82. 删除排序链表中的重复元素 II

    摘要:题目给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中没有重复出现的数字。示例输入输出示例输入输出题解在所有题目中,我觉得链表题目是最简单的。具体画图模拟一道题就可以了。 题目 给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。 示例 1: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示例 2: 输入: 1->...

    xiaodao 评论0 收藏0
  • [Leetcode] Word Search 单词搜索

    摘要:我们可以先用待查单词建立一个字典树,这样我们在从矩阵中某个点开始深度优先搜索时,可以直接用字典树判断当前组成的字符串是否是某个单词的前缀。字典树同样也提供接口,所以同样可以用于判断是否已经搜索到这个词了。 Word Search I 更新的思路与解法请访问:https://yanjia.me/zh/2018/11/... Given a 2D board and a word, f...

    objc94 评论0 收藏0

发表评论

0条评论

Caicloud

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<