当前位置: 首页 > news >正文

LCR 129. 字母迷宫

LCR 129. 字母迷宫

LCR 129. 字母迷宫

参考题解:灵神题解

解题思想

首先我们知道该题需要枚举i=0,1,2,...,n-1j = 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;}
}
http://www.hskmm.com/?act=detail&tid=27667

相关文章:

  • Ignite3 竟然变成分布式数据库了!
  • NUIST 《程序设计基础》 实验1
  • 10.9总结
  • [MIT 6.828] Lab 1 C, Assembly, Tools, and Bootstrapping
  • WCH低功耗蓝牙系列芯片usb烧录故障排查
  • 使用docker构建.net api镜像及nginx反向代理 - binzi
  • 利用sprintf与snprintf巧妙实现数值变量转换为字符串型
  • Helmholtz-Gibbs自由能与熵弹性
  • 日志|电话号码的字母组合|子集|回溯
  • Docker实用篇(初识Docker,Docker的基本操作,Dockerfile自定义镜像,Docker-Compose,Docker镜像仓库) - a
  • ROIR 2023
  • Rust 的验证码图像识别系统设计与实现
  • 【题解】P12992 [GCJ 2022 #1C] Intranets
  • ysyx:pa3.1批处理系统
  • C 语言的验证码图像识别系统实现
  • Nginx典型流控配置示例
  • 基于 C 语言的验证码图像识别系统实现
  • oppoR9m刷Linux系统: 引导知识
  • 操作系统知识点
  • JAVA: Mybatis添加xml执行多行更新语句时报错
  • 安装Docker(CentOS安装Docker,CentOS7安装DockerCompose,Docker镜像仓库) - a
  • 上代码演示下Profile-Guided Optimization (PGO)
  • 所有文档每页的第一行居中对齐
  • 109
  • 一个有趣的网站,可以给自己生成一个奖牌:aitokenawards.com
  • 20232416 2025-2026-1《网络与系统攻防技术》实验一实验报告
  • day008
  • lzr 的区间(interval)
  • IRB-120机械臂socket通信接受上位机指令运行程序段
  • 1.1.1.1 金融市场的定义与功能