79. Word Search (M)

Word Search (M)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.Example:board [ [A,B,C,E], [S,F,C,S], [A,D,E,E] ] Given word ABCCED, return true. Given word SEE, return true. Given word ABCB, return false.题意判断给定矩阵中是否存在一组相邻字符序列能够组成目标字符串。即以矩阵中一字符为起点只能上下左右走且不能重复访问元素判断有无这样一条路径使起点到终点的字符序列正好组成目标字符串。思路回溯法。代码实现classSolution{// 控制左上右下四个方向坐标的变化privateint[]iPlus{0,-1,0,1};privateint[]jPlus{-1,0,1,0};privateintm,n;publicbooleanexist(char[][]board,String word){mboard.length;nboard[0].length;boolean[][]visitednewboolean[m][n];// 先找到与第一个字符相同的位置以该位置为起点搜索路径for(inti0;im;i){for(intj0;jn;j){if(board[i][j]word.charAt(0)){visited[i][j]true;if(search(board,i,j,word,0,visited)){returntrue;}visited[i][j]false;}}}returnfalse;}privatebooleansearch(char[][]board,inti,intj,String word,intindex,boolean[][]visited){if(indexword.length()-1){returntrue;}for(intx0;x4;x){intnextIiiPlus[x];intnextJjjPlus[x];// 判断邻接点是否在矩阵内if(nextI0||nextIm||nextJ0||nextJn){continue;}// 如果邻接点与字符串中下一个字符匹配且尚未被访问则继续递归搜索if(!visited[nextI][nextJ]board[nextI][nextJ]word.charAt(index1)){visited[nextI][nextJ]true;if(search(board,nextI,nextJ,word,index1,visited)){returntrue;}visited[nextI][nextJ]false;}}returnfalse;}}