网站开发公司哪里寻找客源,深圳关键词优化怎么样,wordpress群发文章,中铁建设门户网登录入口手机端79.单词搜索 方法#xff1a;使用回溯
使用dfs函数表示判断以网格的(i.j)位置出发#xff0c;能否搜索到word(k)#xff0c;其中word(k)表示字符串word从第k个字符开始的后缀子串#xff0c;如果能搜索到#xff0c;返回true,反之返回false
如果board[i][j]≠word[k]使用回溯
使用dfs函数表示判断以网格的(i.j)位置出发能否搜索到word(k)其中word(k)表示字符串word从第k个字符开始的后缀子串如果能搜索到返回true,反之返回false
如果board[i][j]≠word[k]当前字符串不匹配直接返回false如果当前已经访问到字符串的末尾且对应字符依然匹配此时直接返回true否则遍历当前位置的所有相邻位置如果从某个相邻位置出发能搜索到子串word[k1,…]则返回true,否则返回false
为了防止重复遍历相同的位置需要额外维护一个visited数组用于标识每个位置是否被访问过每次遍历相邻位置时需要跳过已经被访问的位置
class Solution {public boolean exist(char[][] board, String word) {int m board.length, n board[0].length;boolean[][] visited new boolean[m][n];for(int i 0;im;i){for(int j 0;jn;j){boolean flag dfs(board,word,i,j,visited,0);if(flag){return true;}}}return false;}public boolean dfs(char[][] board, String word,int r,int c,boolean[][] visited,int index){if(board[r][c]!word.charAt(index)){return false;}else if(index word.length() - 1){return true;}visited[r][c] true;boolean result false;int[][] direcions {{0,1},{0,-1},{1,0},{-1,0}}; //定义方位for(int[] dir:direcions){int newrow r dir[0],newcol c dir[1];if(newrow0 newrow board.length newcol0 newcolboard[0].length){if(!visited[newrow][newcol]){boolean flag dfs(board,word,newrow,newcol,visited,index1);if(flag){result true;break;}}}}visited[r][c] false;return result; }
}
