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

相关文章

来自专栏老马说编程

(23) 枚举的本质 / 计算机程序的思维逻辑

前面系列,我们介绍了Java中表示和操作数据的基本数据类型、类和接口,本节探讨Java中的枚举类型。 所谓枚举,是一种特殊的数据,它的取值是有限的,可以枚举出来...

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

Leetcode 241. Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from compu...

1749
来自专栏逆向技术

16位汇编第七讲汇编指令详解第第三讲

                             16位汇编第六讲汇编指令详解第第三讲 1.十进制调整指令 1. 十进制数调整指令对二进制运算的结果进行...

1545
来自专栏深度学习与计算机视觉

C++ 构造函数总结

C++提供了构造函数来处理对象的初始化。构造函数是一种特殊的成员函数,与其他成员函数不同,构造函数不需要用户来调用它,而是建立对象时自动执行。 构造函数的名...

2016
来自专栏xingoo, 一个梦想做发明家的程序员

HDOJ 1005

Number Sequence Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

1788
来自专栏小樱的经验随笔

HDU 1412 {A} + {B}

{A} + {B} Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K...

32715
来自专栏Bingo的深度学习杂货店

Q38 Count and Say

The count-and-say sequence is the sequence of integers with the first five terms...

3387
来自专栏Bingo的深度学习杂货店

Q88 Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one s...

3124
来自专栏Laoqi's Linux运维专列

Python for 循环语句

3518
来自专栏数据结构与算法

1294 全排列

1294 全排列  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给出一个n, ...

2417

扫码关注云+社区