leetcode212. 单词搜索 II
搜索 II 单词
2023-09-27 14:25:55 时间
给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:
输入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。
思路:上一道题改一下,把每一个单词都判断一下即可。
class Solution {
private boolean[][] marked;
// x-1,y
// x,y-1 x,y x,y+1
// x+1,y
private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
// 盘面上有多少行
private int m;
// 盘面上有多少列
private int n;
private String word;
private char[][] board;
//答案数组
Set<String> ans=new HashSet<>();
//判断一个字符
public List<String> findWords(char[][] board, String[] words) {
m = board.length;
if (m == 0)return null;
n = board[0].length;
marked = new boolean[m][n];
this.board = board;
for(String s:words){
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
marked[i][j]=false;
this.word = s;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (dfs(i, j, 0))
ans.add(s);
}
List<String> ansList=new ArrayList<>(ans);
Collections.sort(ansList);
return ansList;
}
private boolean dfs(int i, int j, int start) {
if (start == word.length() - 1) {
return board[i][j] == word.charAt(start);
}
if (board[i][j] == word.charAt(start)) {
marked[i][j] = true;
for (int k = 0; k < 4; k++) {
int newX = i + direction[k][0];
int newY = j + direction[k][1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && !marked[newX][newY]) {
if (dfs(newX, newY, start + 1)) {
return true;
}
}
}
marked[i][j] = false;
}
return false;
}
}
相关文章
- 【LeetCode】解码方法 II [H](记忆化搜索)
- github搜索语法文档
- SharePoint 2013 搜索报错"Unable to retrieve topology component health. This may be because the admin component is not up and running"
- 一次聊个透彻:满二叉树、完全二叉树、二叉搜索树,二叉平衡树
- 【Python排序搜索基本算法】之深度优先搜索、广度优先搜索、拓扑排序、强联通&Kosaraju算法
- 【AI】蒙特卡洛搜索树
- 瞄准大数据营销 神马搜索举办2016营销代理商峰会
- Vue2.5 旅游项目实例11 城市选择页-搜索框布局
- Elasticsearch---基于scroll技术滚动搜索大量数据
- LeetCode_二叉搜索树_中等_95.不同的二叉搜索树 II
- 中国人工智能学会通讯——搜狗搜索:从搜索到问答 1.1 引言
- 中国人工智能学会通讯——互联网搜索技术的前沿探索 5 结束语
- 剑指 Offer II 056. 二叉搜索树中两个节点之和
- LeetCode·每日一题·864.获取所有钥匙的最短路径·广度优先搜索
- ONVIFclient搜索设备获取rtsp解决开发笔记(精华文章)
- ReSharper智能插件,单元测试导航和搜索
- Android 使软键盘的回车按钮变成搜索按钮(Kotlin)
- Android去除按下HOME按键后上方的搜索框
- 基于Vue的淘宝首页跳转商品搜索页的最佳实现方式总结(包括v-model组件间使用技巧总结)