[LeetCode] 79. Word Search
[LeetCode] 79. Word Search
用户1148830
发布于 2018-01-03 17:43:00
发布于 2018-01-03 17:43:00
【原题】 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;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年06月15日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读