-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.java
More file actions
122 lines (92 loc) · 3.21 KB
/
Copy pathSolution.java
File metadata and controls
122 lines (92 loc) · 3.21 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
package test20200926;
import java.util.ArrayList;
import java.util.List;
//前缀树得实现
class Trie {
private boolean is_string=false;
private Trie next[]=new Trie[26];
public Trie(){}
public void insert(String word){//插入单词
Trie root=this;
char w[]=word.toCharArray();
for(int i=0;i<w.length;++i){
if(root.next[w[i]-'a']==null)root.next[w[i]-'a']=new Trie();
root=root.next[w[i]-'a'];
}
root.is_string=true;
}
public boolean search(String word){//查找单词
Trie root=this;
char w[]=word.toCharArray();
for(int i=0;i<w.length;++i){
if(root.next[w[i]-'a']==null)return false;
root=root.next[w[i]-'a'];
}
return root.is_string;
}
public boolean startsWith(String prefix){//查找前缀
Trie root=this;
char p[]=prefix.toCharArray();
for(int i=0;i<p.length;++i){
if(root.next[p[i]-'a']==null)return false;
root=root.next[p[i]-'a'];
}
return true;
}
}
//上面是前缀树
class Solution {
char[][] _board = null;
ArrayList<String> _result = new ArrayList<String>();
Trie root=new Trie();
public List<String> findWords(char[][] board, String[] words) {
// 第一步，构建前缀树
for (String word : words) {
root.insert(word);
}
this._board = board;
// 对于矩阵中的每一个点进行回溯
for (int row = 0; row < board.length; ++row) {
for (int col = 0; col < board[row].length; ++col) {
StringBuilder sb=new StringBuilder();//每次到一个点，就先进建一个Stringbuilder类型
boolean[][] is_visit=new boolean[board.length][board[0].length];
backtracking(row,col,sb,is_visit);
}
}
return this._result;
}
private void backtracking(int row, int col,StringBuilder sb,boolean[][] is_visit) {
//退出回溯的条件，如果row和col是在边缘
if(row>_board.length-1||row<0||col<0||col>_board[0].length-1) return;
//如果当前节点访问过了就return
if(is_visit[row][col]) return;
//如果不是边缘的话，那么sb加入当前的字符
sb.append(_board[row][col]);
is_visit[row][col]=true;
//前缀树包含这个单词的话
if(root.search(sb.toString())) {
if(!_result.contains(sb.toString())){
_result.add(sb.toString());
}
}
//如果前缀树搜索含有这个前缀，就继续上下左右搜索
if(root.startsWith(sb.toString())){
backtracking(row+1,col,sb,is_visit);
backtracking(row-1,col,sb,is_visit);
backtracking(row,col-1,sb,is_visit);
backtracking(row,col+1,sb,is_visit);
}
sb.deleteCharAt(sb.length()-1);
is_visit[row][col]=false;
return;
}
public static void main(String[] args) {
String[] words={
"aaa"
};
char[][] baord={
{'a','a'},
};
System.out.println(new Solution().findWords(baord,words));
}
}