网上建立网站,郑州做网站 熊掌号,天门市电子商务网站建设,aliyun wordpress文章目录 题目方法一#xff1a;递归 回溯 题目 方法一#xff1a;递归 回溯
需要一个标记数组 来标志格子字符是否被使用过了先找到word 的第一个字符在表格中的位置#xff0c;再开始递归递归的结束条件是如果word递归到了最后一个字符了#xff0c;说明能在矩阵中找到单… 文章目录 题目方法一递归 回溯 题目 方法一递归 回溯
需要一个标记数组 来标志格子字符是否被使用过了先找到word 的第一个字符在表格中的位置再开始递归递归的结束条件是如果word递归到了最后一个字符了说明能在矩阵中找到单词剪枝条件 就是如果已经找到单词了 res true 了 后面就不需要递归了还有如果下标越界、当前格子被使用过了、 或者当前格子字符不和当前wordIdenx相同 都直接剪枝 不往下递归了并且在对当前位置进行四个方向递归的时候需要将该位置标志数组置为true代表使用过了在将四个方向递归完了要把当前位置的标志位修改回来回溯
class Solution {boolean res false;//结果标志位int r 0;//全局 矩阵长宽int c 0;boolean[][] usered null;public boolean exist(char[][] board, String word) {r board.length;c board[0].length;// 同一个单元格内的字母不允许被重复使用!!!// 标识字母是否被使用usered new boolean[r][c];char[] chars word.toCharArray();// 将字符串转换为字符数组//在矩阵中找到word第一个字符再进行递归for(int i 0 ; i r ; i)for(int j 0 ; j c ; j){ if(board[i][j] chars[0]) backtrack(board,i,j,chars,0,usered); // 0代表word第一个字符 usered 标记已经使用过的表格}return res;}public void backtrack(char[][] board,int i,int j,char[] chars,int wordIndex,boolean[][] usered){if(res) return;// 已找到答案直接结束if(wordIndex chars.length) {res true ; return;}// 越界 或者不相等// i 和 j 要在矩阵范围内 并且标志位要是fasle 并且当前矩阵格子的字符要是 word当前的字符相等 才会往下递归 否则returnif(i 0 || j 0 || i r-1 || j c-1 || usered[i][j] || board[i][j] ! chars[wordIndex]) return;// 往下递归 说明符合条件// 标记已经被使用usered[i][j] true;//四个方向递归backtrack(board,i-1,j,chars,wordIndex1,usered); backtrack(board,i1,j,chars,wordIndex1,usered); backtrack(board,i,j-1,chars,wordIndex1,usered); backtrack(board,i,j1,chars,wordIndex1,usered); // 回溯恢复状态usered[i][j] false;}}
