首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
拉勾
V2EX  ›  LeetCode

[Leetcode] 79.单词搜索

  •  
  •   Acceml · 177 天前 · 1552 次点击
    这是一个创建于 177 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

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

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

    示例:

    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/video/av25763384?t=813

    熟悉的同学直接看代码吧

    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] = '\0';
            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] = '\0'
            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
    

    热门阅读

    Leetcode 名企之路

    目前尚无回复
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2239 人在线   最高记录 4385   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 15ms · UTC 07:48 · PVG 15:48 · LAX 00:48 · JFK 03:48
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1