public class Find2 {
public int[] dx={1,-1,0,0};
public int[] dy={0,0,1,-1};
class Trie{
Trie[] tries;
String isEnd;
public Trie(){
tries = new Trie[26];
}
}
public boolean[][] vis; //是否判断过
public List<String> res; //答案
public void insert(String word, Trie root){
Trie t = root;
for(int i = 0;i < word.length();i++){
int index = word.charAt(i)-'a';
if(t.tries[index] == null){
t.tries[index] = new Trie();
}
t = t.tries[index];//跳到子节点
}
t.isEnd = word;
}
public List<String> findWords(char[][] board, String[] words) {
//先把单词存入字典树当中
Trie root=new Trie();
for(String word:words){
insert(word,root);
}
res=new ArrayList<String>();
vis=new boolean[board.length][board[0].length];
for(int i=0;i<board.length;++i){ //对board每一个点都进行检索
for(int j=0;j<board[i].length;++j){
dfs(root,i,j,board);
}
}
Collections.sort(res); //需要对结果进行排序
return new ArrayList<String>(res);
}
public void dfs(Trie cur,int x,int y,char[][] board){
//判断边界
if(x<0||y<0||x>=board.length||y>=board[0].length||vis[x][y]){
return;
}
cur=cur.tries[board[x][y]-'a']; //延伸下一个节点
vis[x][y]=true; //把当前设置为走过 不可重复走
if(cur!=null){ //如果当前不为null的话 可以继续检索
if(cur.tries!=null){ //说明到这里已经可以组成一个单词了
res.add(cur.isEnd);
cur.tries=null; //变成null是为了防止重复加入单词
}
for(int i=0;i<4;++i){
dfs(cur,x+dx[i],y+dy[i],board); //四个方向检索
}
}
vis[x][y]=false;
}
public static void main(String[] args) {
String[] words ={"oath","pea","eat","rain"};
char[][] board = {
{'o', 'a', 'a', 'n'},
{'e', 't', 'a', 'e'},
{'i', 'h', 'k', 'r'},
{'i', 'f', 'l', 'v'}
};
Solution m = new Solution();
List<String> a = m.findWords(board,words);
System.out.println(a.toString());
}
}
Java实现 LeetCode 212 单词搜索 II
2023-09-14 08:58:08 时间
相关文章
- Java实现LeetCode 839. 相似字符串组 (深度优先搜索,并查集,图)
- Java实现 LeetCode 819 最常见的单词(暴力)
- Java实现 LeetCode 787 K 站中转内最便宜的航班(两种DP)
- Java实现 LeetCode 779 第K个语法符号(递归)
- Java实现 LeetCode 753 破解保险箱(递归)
- Java实现 LeetCode 745 前缀和后缀搜索(使用Hash代替字典树)
- Java实现 LeetCode 745 前缀和后缀搜索(使用Hash代替字典树)
- Java实现 LeetCode 729 我的日程安排表 I(二叉树)
- Java实现 LeetCode 687 最长同值路径(递归)
- Java实现 LeetCode 622 设计循环队列(暴力大法)
- Java实现 LeetCode 621 任务调度器(暴力大法)
- Java实现 LeetCode 581 最短无序连续子数组(从两遍搜索找两个指针)
- Java实现 LeetCode 581 最短无序连续子数组(从两遍搜索找两个指针)
- Java实现 LeetCode 999 车的可用捕获量(简单搜索)
- Java实现 LeetCode 538 把二叉搜索树转换为累加树(遍历树)
- Java实现 LeetCode 530 二叉搜索树的最小绝对差(遍历树)
- Java实现 LeetCode 462 最少移动次数使数组元素相等 II
- Java实现 LeetCode 449 序列化和反序列化二叉搜索树
- Java实现 LeetCode 449 序列化和反序列化二叉搜索树
- Java实现 LeetCode 443 压缩字符串
- Java实现 LeetCode 424 替换后的最长重复字符
- Java实现 LeetCode 415 字符串相加
- Java实现 LeetCode 241 为运算表达式设计优先级
- Java实现 LeetCode 230 2的幂
- Java实现 LeetCode 230 2的幂
- Java实现 LeetCode 108 将有序数组转换为二叉搜索树
- Java实现 LeetCode 107 二叉树的层次遍历 II(二)
- Java实现 LeetCode 99 恢复二叉搜索树
- Java实现 LeetCode 81 搜索旋转排序数组 II(二)
- Java实现 LeetCode 81 搜索旋转排序数组 II(二)
- Java实现 LeetCode 73 矩阵置零
- Java实现 LeetCode 33 搜索旋转排序数组
- Java实现LeetCode_0007_ReverseInteger
- Java实现 LeetCode 240 搜索二维矩阵 II
- Java实现 LeetCode 212 单词搜索 II
- [Java Spring Data] @JoinTable, @JoinColumn, joinColumns and inverseJoinColumns
- Atitit 搜索蓝牙设备 powershell的实现 java noede.js python 先用脚本语言python nodejs,不好实现。。Java 也不好实现。。 Netcore可以,