79. 单词搜索

这篇具有很好参考价值的文章主要介绍了79. 单词搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

79. 单词搜索,LeetCode_Java版,递归,矩阵,力扣,leetcode,算法,java 解题思路:递归+回溯

首先遍历每一个board中的字符,如果该字符和word的第一个字符相等,就从这个位置进行匹配搜索,如果能够找到word,就返回true,board中可能存在多个字符合word中的第一个字符相等的情况,只要任一个位置能够匹配到,就直接返回true

因为同一个单元格内的字符不能重复使用,需要使用一个额外的数组标记那些单元格被访问过了

具体匹配搜索递归算法如下:

  1. 定义递归函数:process(char[][] board, String word, int x, int y, int index)
    1. 含义:从board[x][y]开始与word的第index个位置往后继续匹配,如果能够找到匹配的字符,返回true,否则返回false
  2. 递归终止的条件:
    1. 如果 board[x][y] != word.charAt(index):显然不匹配,返回false
    2. 否则,board当前位置的字符和word的第index个字符匹配,如果index==word.length()-1:已经全部匹配了,返回true
  3. 否则board[x][y]与 word.charAt(index)匹配,继续寻找board中下一个位置与word.charAt(index+1)匹配:
    1. 下一个位置有两个(边界情况,只能向两个方向走)或四个可选择的位置,依次遍历所有可能的位置,假设下一个位置为board[nextX][nextY]:
      1. 如果 flag[nextX][nextY]=false并且 board[nextX][nextY] == word.charAt(index+1):
        1. 令flag[nextX][nextY] = true
        2. result = process(board,word,nextX,nextY,index+1)
        3. 如果result=true,直接返回true
        4. 否则,说明从board[nextX][nextY]位置开始搜索没有匹配到,进行回溯,令flag[nextX][nextY] = flase
    2. 所有位置都没有匹配,返回false

AC代码:

class Solution {
    //标记哪些位置已经访问过
    boolean[][] flag;
    //四个方向
    int[][] direct = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public boolean exist(char[][] board, String word) {
        if (board.length*board[0].length<word.length()){
            return false;
        }
        flag = new boolean[board.length][board[0].length];
        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[0].length; y++) {
                if (board[x][y] == word.charAt(0)) {
                    flag[x][y] = true;
                    boolean result = process(board, word, x, y, 0);
                    if (result) {
                        return true;
                    }
                    flag[x][y] = false;
                }
            }
        }
        return false;
    }

    public boolean process(char[][] board, String word, int x, int y, int index) {
        if (board[x][y]!=word.charAt(index)){
            return false;
        }else if (index==word.length()-1){
            return true;
        }

        for (int i = 0; i < 4; i++) {
            int nextX = x + direct[i][0];
            int nextY = y + direct[i][1];
            if (nextX >= 0 && nextX < board.length
                    && nextY >= 0 && nextY < board[0].length
                    && !flag[nextX][nextY]
                    && board[nextX][nextY] == word.charAt(index + 1)) {
                flag[nextX][nextY] = true;
                boolean result = process(board, word, nextX, nextY, index + 1);
                if (result) {
                    return true;
                }
                flag[nextX][nextY] = false;
            }
        }
        return false;
    }
}

79. 单词搜索,LeetCode_Java版,递归,矩阵,力扣,leetcode,算法,java

 文章来源地址https://www.toymoban.com/news/detail-641743.html

 

 

 

到了这里,关于79. 单词搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode做题笔记79单词搜索

    给定一个  m x n  二维字符网格  board  和一个字符串单词  word  。如果  word  存在于网格中,返回  true  ;否则,返回  false  。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不

    2024年02月12日
    浏览(36)
  • 算法leetcode|79. 单词搜索(rust重拳出击)

    给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

    2024年02月09日
    浏览(59)
  • 递归回溯两个例题:1.数组组合 2.在矩阵中搜索单词

    题目1:组合 给定两个整数 n 和 k ,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 输入:n = 4, k = 2 输出: [   [2,4],   [3,4],   [2,3],   [1,2],   [1,3],   [1,4], ]  解题思路: 1.定义一个temp数组,存放临时的组合结果 2.两种选择:1.选择当前元素2.不选

    2024年02月15日
    浏览(43)
  • 79. 单词搜索

    题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台  解题思路:递归+回溯 首先遍历每一个board中的字符,如果该字符和word的第一个字符相等,就从这个位置进行匹配搜索,如果能够找到word,就返回true,board中可能存在多个字符合word中的第一个字符相等的情况,

    2024年02月13日
    浏览(32)
  • 01 矩阵(力扣)多源广度优先搜索 JAVA

    给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 输入:mat = [[0,0,0],[0,1,0],[0,0,0]] 输出:[[0,0,0],[0,1,0],[0,0,0]] 输入:mat = [[0,0,0],[0,1,0],[1,1,1]] 输出:[[0,0,0],[0,1,0],[1,2,1]] 提示

    2024年02月15日
    浏览(39)
  • 递归算法学习——N皇后问题,单词搜索

    目录 ​编辑 一,N皇后问题 1.题意 2.解释 3.题目接口 4.解题思路及代码 二,单词搜索 1.题意 2.解释 3.题目接口 4.思路及代码 1.题意 按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题  研究的是如何将  n  个皇后放置在  n×n  的

    2024年02月09日
    浏览(41)
  • 力扣211. 添加与搜索单词 - 数据结构设计

    思路: 设计一棵字典树,每个节点存放单词的一个字符,节点放一个标记位,如果是单词结束则标记; 字典树插入: 字典树默认有 26 个 slot 槽代表 a - z; 遍历单词,如果字符对应槽存在则迭代到子节点,如果不存在则创建; 在单词结尾的节点,将 flag 标记; 字典树查询:

    2024年01月20日
    浏览(55)
  • 算法学习——LeetCode力扣补充篇11(64. 最小路径和、48. 旋转图像 、169. 多数元素、394. 字符串解码、240. 搜索二维矩阵 II )

    64. 最小路径和 - 力扣(LeetCode) 描述 给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例 示例 1: 输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→

    2024年04月23日
    浏览(38)
  • leetcode 74. 搜索二维矩阵(java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/search-a-2d-matrix 给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非递减顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回

    2024年02月16日
    浏览(45)
  • java数据结构与算法刷题-----LeetCode240. 搜索二维矩阵 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 法一:把整个数组遍历一遍,时间复杂度O(m*n) 法二:每一行用二分搜索,那么时间复杂度就是O(m * l o g 2 n log_2{n} l o g

    2024年01月22日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包