LCR 129. 字母迷宫

LCR 129. 字母迷宫

LCR 129. 字母迷宫

参考题解：灵神题解

解题思想

首先我们知道该题需要枚举i=0,1,2,...,n-1，j = 0,1,2,3,...,m-1，以(i,j)为起点开始搜索

同时我们还需要知道target匹配到了哪个字符，定义一个记录参数k

定义一个dfs(i, j, k)深度搜索函数表示当前这个格子，是否匹配target(k)，匹配返回true，否则false

对于dfs(i,j,k)分类讨论：

• 如果grid[i,j]不等于target[k]，返回false
• 如果参数k等于target的长度 - 1，即k=len(target)-1，返回true
• 枚举(i,j)的相邻的四个格子(x,y)，如果(x,y)没有出界，则递归dfs(x,y,k+1)，如果返回true，那么dfs(i,j,k)就一定也是true
• 如果四个相邻格子都是false，那就返回false

避免重复访问细节

为了避免重复访问同一个格子，可以使用vis数组标记每一个访问过的字符，但是更方便的可以直接将grid[i,j]先设为0，如果返回false直接恢复现场，返回true就不用恢复现场，因为已经匹配到了

代码展示：

public boolean dfs( int i, int j, int k, char[][] grid, char[] target) {// 字符串数组的字符和 target 中的不匹配if(grid[i][j] != target[k]) {return false;}// 成功匹配记录数字 k 的值等于 target 的长度if(k == target.length - 1) {return true;}grid[i][j] = 0; // 标记访问过for(int[] d: DIRS) {int x = i + d[0];int y = j + d[1];if(0 <= x && x <= grid.length - 1 && 0 <= y && y <= grid[x].length - 1 && dfs(x, y, k + 1, grid, target)) {return true; // 成功搜到}}// 没搜到grid[i][j] = target[k]; // 恢复现场return false;}

可优化的点

优化1

如果grid中的某个字符出现的次数比target中对应的字符出现的次数大，返回false

// 优化1
char[] t = target.toCharArray();
int[] targetCnt = new int[128];
for(int c: t) {if(++targetCnt[c] > cnt[c]) {return false; // grid 某个字符和 target 对应的字符出现次数不符}
}

优化2

假设target的首字符出现的次数为x，末尾字符出现的次数为y，如果x > y，那么就将target反转，这样在一开始就满足了grid[i][j] != target[k]，不用接着往后搜索了

// 优化 2
if(cnt[t[t.length - 1]] < cnt[t[0]]) {t = new StringBuilder(target).reverse().toString().toCharArray();
}

最终代码展示

class Solution {private static final int[][] DIRS = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};public boolean wordPuzzle(char[][] grid, String target) {// 用数组代替哈希表int[] cnt = new int[128];for (char[] row : grid) {for (char c : row) {cnt[c]++; // 将cnt[c]的值加1，做好 key-value}}// 优化1char[] t = target.toCharArray();int[] targetCnt = new int[128];for(int c: t) {if(++targetCnt[c] > cnt[c]) {return false; // grid 某个字符和 target 对应的字符出现次数不符}}// 优化 2if(cnt[t[t.length - 1]] < cnt[t[0]]) {t = new StringBuilder(target).reverse().toString().toCharArray();}for(int i = 0; i < grid.length; i++) {for(int j = 0; j < grid[i].length; j++) {if(dfs(i, j, 0, grid, t)) {return true; // 搜到了}}}return false;}public boolean dfs( int i, int j, int k, char[][] grid, char[] target) {// 字符串数组的字符和 target 中的不匹配if(grid[i][j] != target[k]) {return false;}// 成功匹配记录数字 k 的值等于 target 的长度if(k == target.length - 1) {return true;}grid[i][j] = 0; // 标记访问过for(int[] d: DIRS) {int x = i + d[0];int y = j + d[1];if(0 <= x && x <= grid.length - 1 && 0 <= y && y <= grid[x].length - 1 && dfs(x, y, k + 1, grid, target)) {return true; // 成功搜到}}// 没搜到grid[i][j] = target[k]; // 恢复现场return false;}
}