[LeetCode] 79. Word Search

【原题】 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. 【解释】 给定一个二维的字符数组和一个单词,要求返回该单词是否可以在该字符数组中找到(查找尽可以上下左右查找) 【思路】 从数组的每一个位置上下左右递归查找,如果有任意方向找到则返回true,否则从下一个位置开始查找。

public class Solution {
  public static boolean exitCore(char[][] board,String word, int index, int row,int col,boolean[][] isVisit){
        if(index==word.length()) return true;//前面所有的元素都相等,则找到
            if(row<0||col<0||row>=board.length||col>=board[0].length||
                board[row][col]!=word.charAt(index)||isVisit[row][col])
            return false;
        boolean flag=false;
        isVisit[row][col]=true;
        flag=exitCore(board, word, index+1,row+1,col,isVisit)||exitCore(board, word, index+1,row,col+1,isVisit)
                ||exitCore(board, word, index+1,row-1,col,isVisit)||exitCore(board, word, index+1,row,col-1,isVisit);
        if(flag) return flag;
        isVisit[row][col]=false;//没有找到,重新将该元素置为未访问
        return false;
    }
     public static boolean exist(char[][] board, String word) {
            int m=board.length,n=board[0].length;
            boolean[][] isVisit=new boolean[m][n];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++)
                        if(exitCore(board,word,0,i,j,isVisit)) return true;

            }
                return false;
        }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏九彩拼盘的叨叨叨

CSS hack总结

有时,我们为了让一些外观在不同浏览器中做保持一致。就不得不用css hack。下面是常用的css hack。

742
来自专栏技术墨客

React Web组件

从概念上说,React 和 Web组件 分别用于解决不同的问题。Web组件提供了强大的封装特性来支持其可重复使用性,而React提供了一系列声明性(declar...

622
来自专栏计算机视觉与深度学习基础

Leetcode 84 Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the...

1699
来自专栏ACM算法日常

How many integers can you find(容斥原理) - HDU 1796

看这题之前先复习一下容斥原理,不然肯定看不懂,呃,如果第一次接触容斥原理的题,可能弄懂了容斥原理你还是看不懂代码,是的,等会你就知道了。

732
来自专栏更流畅、简洁的软件开发方式

使用接口来统一控件的取值、赋值和初始化

      这里说的控件主要指的是文本框、下拉列表框这一类的控件,用户使用这些控件输入数据,然后我们需要提取这些数据进行处理。但是不同的控件有不同的取值方式,比...

1876
来自专栏开发与安全

从零开始学C++之运算符重载(二):++运算符重载、!运算符重载、赋值运算符重载

一、++运算符重载 前置++运算符重载 成员函数的方式重载,原型为: 函数类型 & operator++(); 友元函数的方式重载,原型为: friend...

2130
来自专栏技术墨客

React学习(11)—— 高阶应用:Web组件

从概念上说,React 和 Web组件 分别用于解决不同的问题。Web组件提供了强大的封装特性来支持其可重复使用性,而React提供了一系列声明性(declar...

642
来自专栏noteless

java内部类深入详解 内部类的分类 特点 定义方式 使用

java内部类 内部类的分类 特点  定义方式 使用   外部类调用内部类 多层嵌套内部类  内部类访问外部类属性  接口中的内部类  内部类的继承  内部类的...

691
来自专栏LanceToBigData

JavaSE(七)之内部类

上一篇我们学习了接口还有访问控制,在以后的工作中接口是我们经常要碰到的,所以一定要多去回顾。接下来介绍一下内部类。很多时候我们创建类的对象的时候并不需要使用很多...

1749
来自专栏前端小叙

vue获取dom元素注意问题

mounted(){ setTimeout(()=>{ this.contentToggle(); },10...

2798

扫码关注云+社区