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

[Leetcode] 79.单词搜索

  •  
  •   Acceml ·
    Acceml · 2018-09-27 21:58:30 +08:00 · 6606 次点击
    这是一个创建于 2009 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

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

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

    示例:

    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 名企之路

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2886 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 11:34 · PVG 19:34 · LAX 04:34 · JFK 07:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.