力扣面试150题--单词搜索

Day 74

题目描述

思路

初次思路：利用回溯的思想，具体做法如下：

1. 设置一个标记的二维数组，用来记录已经被访问的元素
2. 下面是back函数的内容，传入参数有back(char[][] board,String word,int[][] num,int n,int i,int j) board是字母表，word为要寻找的单词，num为标记数组，n为这轮back访问的word中该序号的字母，i，j为上一个字母在字母表中的坐标。
3. 确定终止条件，只要访问完单词的长度即可
4. 获取这轮需要寻找的字母beg
5. 二重循环寻找与这个字母相同并且未被访问的元素坐标，
6. 如果这是单词的第一个元素，直接寻找下一个字母
7. 如果这是单词第二及以后的单词，与传进来的坐标i，j判断是否相邻

class Solution {public boolean res=false;public boolean exist(char[][] board, String word) {if(word.length()==0){return true;}int n=word.length();char beg=word.charAt(0);int[][]num=new int[board.length][board[0].length];for(int i=0;i<board.length;i++){for (int j = 0; j < board[i].length; j++) {num[i][j]=0;}}back(board,word,num,0,-1,-1);return res;}public void back(char[][] board,String word,int[][] num,int n,int i,int j){if(n==word.length()){res=true;return;}char beg=word.charAt(n);for (int k = 0; k < board.length; k++) {for (int l = 0; l < board[k].length; l++) {if(beg==board[k][l]&&num[k][l]==0){if(i==-1 && j==-1){//第一个元素num[k][l]=1;back(board,word,num,n+1,k,l);num[k][l]=0;}else{//第二个及以后的元素if((k==i-1&&l==j)||(k==i&&l==j-1)||(k==i&&l==j+1)||(k==i+1&&l==j)){//相邻num[k][l]=1;back(board,word,num,n+1,k,l);num[k][l]=0;}}}else{continue;}}}}
}

**优化思路：**修改上方寻找相邻元素的做法，传入坐标后，只判断相邻是否有目标字母。

class Solution {public boolean res=false;public boolean exist(char[][] board, String word) {if(word.length()==0){return true;}int n=word.length();char beg=word.charAt(0);int[][]num=new int[board.length][board[0].length];for(int i=0;i<board.length;i++){for (int j = 0; j < board[0].length; j++) {num[i][j]=0;}}for(int i=0;i<board.length;i++){for(int j=0;j<board[0].length;j++){if(board[i][j]==beg){num[i][j]=1;back(board,word,num,1,i,j);num[i][j]=0;}if(res){return true;}}}return false;}public void back(char[][] board,String word,int[][] num,int n,int i,int j){if(n==word.length()){res=true;return;}char beg=word.charAt(n);int x,y;x=i-1;y=j;if(x>=0&&board[x][y]==beg&&num[x][y]==0){num[x][y]=1;back(board,word,num,n+1,x,y);num[x][y]=0;}x=i;y=j-1;if(y>=0&&board[x][y]==beg&&num[x][y]==0){num[x][y]=1;back(board,word,num,n+1,x,y);num[x][y]=0;}x=i;y=j+1;if(y<board[0].length&&board[x][y]==beg&&num[x][y]==0){num[x][y]=1;back(board,word,num,n+1,x,y);num[x][y]=0;}x=i+1;y=j;if(x<board.length&&board[x][y]==beg&&num[x][y]==0){num[x][y]=1;back(board,word,num,n+1,x,y);num[x][y]=0;}}
}