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

深度优先检索:单词搜索

问题:

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

 

思想:

深度优先算法加回溯算法完成

 

代码:

 

class Solution {public boolean exist(char[][] board, String word) {if(board.length < 1){return false;}int n = board.length;int m = board[0].length;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(dfs(board,word,0,i,j)){return true;}}}return false;}public boolean dfs(char[][] board,String word,int index,int x,int y){if(x>=board.length || x < 0||y >=board[0].length||y<0||board[x][y]=='#'||board[x][y] != word.charAt(index)){return false;}if(index == word.length() - 1){return true;}else{char temp = board[x][y];board[x][y] = '#';boolean flag = dfs(board,word,index+1,x+1,y)||dfs(board,word,index+1,x-1,y) || dfs(board,word,index+1,x,y-1) || dfs(board,word,index+1,x,y+1);board[x][y] = temp;return flag;}}
}

 

http://www.hskmm.com/?act=detail&tid=15577

相关文章:

  • WoTerm、WindTerm及putty的性能测试对比
  • CF333E Summer Earnings
  • 一文看懂Playwright MCP如何引爆AI智能体爆发
  • 从nano banana模型到更加真实的3D打印技术
  • 职业卡点怎么破?3个月私教服务助你升级技能与面试技巧
  • OI?原来这么简单-语法算法入门篇
  • 跨境tk避雷proxy-cheap代理服务商!!!
  • Rouyan:使用WPF/C#构建的基于LLM的快捷翻译小工具
  • BM25 关键词检索算法
  • 记录用户业务请求日志
  • [C++:类的默认成员函数——Lesson7.const成员函数] - 指南
  • 详细介绍:Xilinx系列FPGA实现12G-SDI音视频编解码,支持4K60帧分辨率,提供2套工程源码和技术支持
  • 使用 VMware Workstation 安装 CentOS-7 虚拟机
  • K12教育 和 STEAM教育
  • AT_arc167_c [ARC167C] MST on Line++
  • Lombok无法使用get set方法
  • redis的哈希扩容
  • vite tailwindcss配置
  • 在Vona ORM中实现多数据库/多数据源
  • 实用指南:python全栈-数据可视化
  • sql over()函数使用
  • Git回退版本 reset、revert、read-tree、restore
  • Avalonia 背景颜色Transparent在用户界面设计中对悬浮效果影响的总结
  • 飞书 燕千云焕新上线,飞书用户即刻试用ITSM工具
  • 如果使用微软 Azure 托管的 OpenAI 服务
  • Python类
  • 什么是文件外发审批?主要有哪几种关键流程?
  • VPX处理板设计原理图:9-基于DSP TMS320C6678+FPGA XC7V690T的6U VPX信号处理卡 C6678板卡, XC7VX690T板卡, VPX处理板
  • VitePress 添加友链界面
  • 跨网文件摆渡软件:企业数据安全高效传输的关键解决方案!