宜春市住房和城乡建设局网站,外贸网站如何seo,营销推广方案模板,微信小程序cms系统给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 单词必须按照字母顺序#xff0c;通过相邻的单元格内的字母构成#xff0c;其中“相邻”单元格是那些水平相邻或垂直相… 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。 单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 这种是不是和岛屿搜索的类型题是相似的每个点都有8个位置的选择这种类型题就可以用我们上次讲的岛屿数量的解法通过深度优先遍历dfs进行解决 //设置方向 上右下左int[] xnum{-1,0,1,0};int[] ynum{0,1,0,-1};
我们可以维护一个visited数组防止走回头路 boolean[][] visited; 递归函数中入参的变量我们看需要哪些原数组肯定是需要的然后我们也需要知道我们已经遍历到哪个点了因为我们要找的是字符串我们也要知道当前遍历到字符串的哪个索引上函数签名如下 private boolean dfs(char[][] board, String word, int startIndex, int x, int y) {} 如果当前遍历到字符串索引的最后一位且网格中也有相同的字符那就说明该路径我们在网格中是可以找到的如果找不到直接返回false,如果当前不是字符串的最后一个索引对应的位置在从当前元素的相邻元素不断的去进行寻找直到找到返回true或者fasle为止
源码如下 //设置方向 上右下左int[] xnum{-1,0,1,0};int[] ynum{0,1,0,-1};boolean[][] visited;int row;int column;public boolean exist(char[][] board, String word) {//对入参进行判断if(boardnull||board.length0||board[0].length0){return false;}//从每一个点都开始进行遍历rowboard.length;columnboard[0].length;visitednew boolean[row][column];for (int i 0; i row; i) {for (int j 0; j column; j) {//如果存在一种情况则返回trueif(dfs(board,word,0,i,j)){return true;}}}return false;}private boolean dfs(char[][] board, String word, int startIndex, int x, int y) {if(startIndexword.length()-1){if(word.charAt(startIndex)board[x][y]){return true;}}if(word.charAt(startIndex)!board[x][y]){return false;}else{//向四个方向进行寻找visited[x][y]true;for (int i 0; i 4; i) {int newxxxnum[i];int newyyynum[i];//如果越界的话则不需要进行考虑if(newx0||newxrow||newy0||newycolumn||visited[newx][newy]){continue;}if(dfs(board,word,startIndex1,newx,newy)){return true;} }//回溯visited[x][y]false;}return false;}
