[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 条评论
登录 后参与评论

相关文章

来自专栏算法修养

UESTC 485 Game(康托,BFS)

Today I want to introduce an interesting game to you. Like eight puzzle, it is a...

2677
来自专栏架构之路

判断栈的出栈顺序合法性

栈的出栈顺序合法性是指给定一系列元素,如1 - N,按照从小到大的方式入栈,每个元素的出栈时机不定。题目给定一个出栈顺序,我们来判断这个出栈顺序有没有可能发生。...

1983
来自专栏行者常至

009.多线程-AtomicInteger

版权声明:本文为博主原创文章,允许转载,请标明出处。

542
来自专栏java闲聊

JDK1.8 LinkedList 源码解析

1484
来自专栏个人分享

Java方法总结与源码解析(未完待续)

源码通过获取字符串的长度,遍历每个字符,将传入的字符进行比较,如果与需要截取的字符相同,则调用substring方法。

652
来自专栏小灰灰

JDK容器学习之LinkedList:底层存储&读写逻辑

LinkedList的底层结构及读写逻辑 链表容器,通常适用于频繁的新增删除,遍历的方式访问数据元素的场景 LinkedList 底层数据结构为链表,非线程安...

1868
来自专栏云霄雨霁

数据结构----栈

1440
来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列13

一、说出一些常用的类,包,接口,请各举5个 常用的类:BufferedReader BufferedWriter FileReader FileWirter ...

2673
来自专栏Java 源码分析

LinkedList 源码分析

LinkedList 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,...

2724
来自专栏编程

详解栈及其实现

转自:melonstreet http://www.cnblogs.com/QG-whz/p/5170418.html 栈的特点 栈(Stack)是一种线性存储...

2076

扫码关注云+社区