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;}
}