搜狐一开始把网站当做什么来做,成都网站建设,阜康市建设银行网站,wordpress 当数据库79.给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 单词必须按照字母顺序#xff0c;通过相邻的单元格内的字母构成#xff0c;其中“相邻”单元格是那些水平相邻或垂直… 79.给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。 单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例 1 输入board [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word “ABCCED” 输出true 示例 2 输入board [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word “SEE” 输出true 示例 3 输入board [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word “ABCB” 输出false 我的思路首先由于不确定从哪个点开始可以构成目标单词所以肯定是枚举每个点作为起点。这种路径问题想都不用想肯定是 dfs先想一下入参当我从某个点开始找那肯定入参要有坐标我们还需要知道已经匹配到哪一步了所以用一个数字来表示已匹配的单词字符数接着就是出口首先出了边界肯定要返回 false由于题目说不能重复使用所以递归过程中遇到重复的坐标也要返回 false当然最容易想到的当前坐标的字符和目标单词当前匹配字符不匹配也肯定返回 false。当匹配到最后一个字符时还没有返回 false自然是只能返回 true 了。最后就是 dfs 的每一步的内容。由于方向不定所以往上下左右寻找下一位匹配字符有一个满足就继续寻找即可。 String WORD;char[][] BOARD;int m,n;public boolean exist(char[][] board, String word) {BOARD board;WORD word;mboard.length;nboard[0].length;for(int i0;im;i){for(int j0;jn;j){if(dfs(i,j,0))return true;}}return false;}public boolean dfs(int x,int y,int cur){// 超过边界if(x 0 || x m || y 0 || y n)return false;// word 的某一位字符和当前坐标处字符不匹配if(WORD.charAt(cur) ! BOARD[x][y])return false;if(cur WORD.length()-1 )return true;// 为了防止重复将字符置为空这样下次和坐标处字符必定不匹配BOARD[x][y] \0;boolean up dfs(x-1,y,cur1);boolean down dfs(x1,y,cur1);boolean left dfs(x,y-1,cur1);boolean right dfs(x,y1,cur1);// 还原字符BOARD[x][y] WORD.charAt(cur);return up || down || left || right;}上面的还原字符有必要说一下这是我唯一没想到的一点。无论你用什么方式来防止重复访问某个坐标你都需要还原这一步。我原本以为用一个 hashSet 记录该坐标是否访问过下一次访问直接返回 false 即可。但是假设一条错误的路径会经过比如坐标 [2,2]然后将其标记为已访问过最终该路径结果返回 false。但是有可能正确的路径也包含了这个坐标 [2,2]但是由于错误路径提前把这个坐标访问掉了所以你正确的路径反而没法访问了到这个坐标直接返回了 false所以需要还原。之所以这样能还原我个人理解是因为比如还是 [2,2] 这个点错误路径为 [1,2]-[2,2]-... 然后返回 false。而正确路径比如为 [1,2]-[1,3]-[2-3]-[2,2]-... 然后返回 true。在错误路径代码执行期间在递归的第二层把 [2,2] 置空之后的每一层递归都将无法访问这个点而正确路径在递归的第四层才访问这个点这时候当然无法访问了而还原也就意味着当那些错误的可能性被否决只要你能够回溯到第二层递归就代表我在第二层就把 [2,2] 用掉是不可行的也就是说在第二层不能把 [2,2] 用掉。那么我自然要给你重新访问 [2,2] 的机会所以有还原操作。也就是说我给错误路径访问 [2,2]他不中用那我换个人给机会肯定要公平地也给你一次访问 [2,2] 的机会。
