Java实现 LeetCode 212 单词搜索 II
2023-09-14 08:58:08 时间
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 813 最大平均值和的分组 (DFS+DP记忆化搜索)
- Java实现 LeetCode 811 子域名访问计数 (暴力)
- Java实现 LeetCode 808 分汤 (暴力模拟)
- Java实现 LeetCode 798 得分最高的最小轮调 (暴力分析)
- Java实现 LeetCode 745 前缀和后缀搜索(使用Hash代替字典树)
- Java实现 LeetCode 714 买卖股票的最佳时机含手续费(动态规划 || 迭代法)
- Java实现 LeetCode 701 二叉搜索树中的插入操作(遍历树)
- Java实现 LeetCode 669 修剪二叉搜索树(遍历树)
- Java实现 LeetCode 669 修剪二叉搜索树(遍历树)
- Java实现 LeetCode 662 二叉树最大宽度(递归)
- Java实现 LeetCode 643 子数组最大平均数 I(滑动窗口)
- Java实现 LeetCode 623 在二叉树中增加一行(遍历树)
- Java实现 LeetCode 581 最短无序连续子数组(从两遍搜索找两个指针)
- Java实现 LeetCode 999 车的可用捕获量(简单搜索)
- Java实现 LeetCode 537 复数乘法(关于数学唯一的水题)
- Java实现 LeetCode 504 七进制数
- Java实现 LeetCode 450 删除二叉搜索树中的节点
- Java实现 LeetCode 343 整数拆分(动态规划入门经典)
- Java实现 LeetCode 306 累加数
- Java实现 LeetCode 179 最大数
- Java实现 LeetCode 173 二叉搜索树迭代器
- Java实现 LeetCode 173 二叉搜索树迭代器
- Java实现 LeetCode 105 从前序与中序遍历序列构造二叉树
- Java实现 LeetCode 98 验证二叉搜索树
- Java实现 LeetCode 98 验证二叉搜索树
- Java实现 LeetCode 81 搜索旋转排序数组 II(二)
- Java实现 LeetCode 74 搜索二维矩阵
- Java实现 LeetCode 240 搜索二维矩阵 II
- 【JAVA】java中split以"." 、""、“|”分隔字符串
- Atitit.视频文件加密的方法大的总结 java c# php
- 【Java】java 环境配置(详细教程)
- Java开发技术之成为高级java工程师必须学习的三个技术