代码应用：
wordTrie.txt(工具类)：
package com.xq.algorithm;
import java.util.ArrayList;
import java.util.List;
/**
*
* <p> :</p>
* <p>De ion: 单词Trie树
* </p>
* @createDate：2013-10-17
* @author xq
* @version 1.0
*/
public class WordTrie {
/**trie树根*/
private TrieNode root = new TrieNode();
/**英文字符串正则匹配*/
static String englishPattern=\"^[A-Za-z]+$\";
/**中文正则匹配*/
static String chinesePattern=\"[\\u4e00-\\u9fa5]\";
static int ARRAY_LENGTH=26;
static String zeroString=\"\";
/**
*
* @ : addWord
* @De ion: add word
* @param @param word
* @return void
* @throws
*/
public void addWord(String word) {
if(word==null || \"\".equals(word.trim())){
throw new IllegalArgumentException(\"word can not be null!\");
}
if(!word.matches(englishPattern)){
throw new IllegalArgumentException(\"word must be english!\");
}
addWord(root, word);
}
/**
*
* @ : addWord
* @De ion:add word to node
* @param @param node
* @param @param word
* @return void
* @throws
*/
private void addWord(TrieNode node, String word) {
if (word.length() == 0) { // if all characters of the word has been
// added
node.count++;
node.nodeState=1;
} else {
node.prefixCount++;
char c = word.charAt(0);
c = Character.toLowerCase(c);
int index = c - \'a\';
if(index>=0 && index<ARRAY_LENGTH){
if (node.next[index] == null) {
node.next[index] = new TrieNode();
}
// go the the next character
addWord(node.next[index], word.substring(1));
}
}
}
/**
*
* @ : prefixSearchWord
* @De ion: 前缀搜索
* @param @param word
* @param @return
* @return List<String>
* @throws
*/
public List<String> prefixSearchWord(String word){
if(word==null || \"\".equals(word.trim())){
return new ArrayList<String>();
}
if(!word.matches(englishPattern)){
return new ArrayList<String>();
}
char c = word.charAt(0);
c = Character.toLowerCase(c);
int index = c - \'a\';
if(root.next!=null && root.next[index]!=null){
return depthSearch(root.next[index],new ArrayList<String>(),word.substring(1),\"\"+c,word);
}else{
return new ArrayList<String>();
}
}
/**
*
* @ : searchWord
* @De ion: 搜索单词,以a-z为根,分别向下递归搜索
* @param @param word
* @param @return
* @return List<String>
* @throws
*/
public List<String> searchWord(String word){
if(word==null || \"\".equals(word.trim())){
return new ArrayList<String>();
}
if(!word.matches(englishPattern)){
return new ArrayList<String>();
}
char c = word.charAt(0);
c = Character.toLowerCase(c);
int index = c - \'a\';
List<String> list=new ArrayList<String>();
if(root.next==null){
return list;
}
for(int i=0;i<ARRAY_LENGTH;i++){
int j=\'a\'+i;
char temp=(char)j;
if(root.next[i]!=null){
if(index==i){
fullSearch(root.next[i],list,word.substring(1),\"\"+temp,word);
}else{
fullSearch(root.next[i],list,word,\"\"+temp,word);
}
}
}
return list;
}
/**
*
* @ : fullSearch
* @De ion: 匹配到对应的字母,则以该字母为字根,继续匹配完所有的单词。
* @param @param node
* @param @param list 保存搜索到的字符串
* @param @param word 搜索的单词.匹配到第一个则减去一个第一个,连续匹配,直到word为空串.若没有连续匹配,则恢复到原串。
* @param @param matchedWord 匹配到的单词
* @param @return
* @return List<String>
* @throws
*/
private List<String> fullSearch(TrieNode node,List<String> list,String word,String matchedWord,String inputWord){
if(node.nodeState==1 && word.length()==0){
list.add(matchedWord);
}
if(word.length() != 0){
char c = word.charAt(0);
c = Character.toLowerCase(c);
int index = c - \'a\';
for(int i=0;i<ARRAY_LENGTH;i++){
if(node.next[i]!=null){
int j=\'a\'+i;
char temp=(char)j;
if(index==i){
//连续匹配
fullSearch(node.next[i], list, word.substring(1), matchedWord+temp,inputWord);
}else{
//未连续匹配,则重新匹配
fullSearch(node.next[i], list, inputWord, matchedWord+temp,inputWord);
}
}
}
}else{
if(node.prefixCount>0){
for(int i=0;i<ARRAY_LENGTH;i++){
if(node.next[i]!=null){
int j=\'a\'+i;
char temp=(char)j;
fullSearch(node.next[i], list, zeroString, matchedWord+temp,inputWord);
}
}
}
}
return list;
}
/**
*
* @ : depthSearch
* @De ion: 深度遍历子树
* @param @param node
* @param @param list 保存搜索到的字符串
* @param @param word 搜索的单词.匹配到第一个则减去一个第一个,连续匹配,直到word为空串.若没有连续匹配,则恢复到原串。
* @param @param matchedWord 匹配到的单词
* @param @return
* @return List<String>
* @throws
*/
private List<String> depthSearch(TrieNode node,List<String> list,String word,String matchedWord,String inputWord){
if(node.nodeState==1 && word.length()==0){
list.add(matchedWord);
}
if(word.length() != 0){
char c = word.charAt(0);
c = Character.toLowerCase(c);
int index = c - \'a\';
//继续完全匹配,直到word为空串,否则未找到
if(node.next[index]!=null){
depthSearch(node.next[index], list, word.substring(1), matchedWord+c,inputWord);
}
}else{
if(node.prefixCount>0){//若匹配单词结束,但是trie中的单词并没有完全找到,需继续找到trie中的单词结束.
//node.prefixCount>0表示trie中的单词还未结束
for(int i=0;i<ARRAY_LENGTH;i++){
if(node.next[i]!=null){
int j=\'a\'+i;
char temp=(char)j;
depthSearch(node.next[i], list, zeroString, matchedWord+temp,inputWord);
}
}
}
}
return list;
}
class TrieNode {
/**
* trie tree word count
*/
int count=0;
/**
* trie tree prefix count
*/
int prefixCount=0;
/**
* 指向各个子树的指针,存储26个字母[a-z]
*/
TrieNode[] next=new TrieNode[26];
/**
* 当前TrieNode状态 ,默认 0 , 1表示从根节点到当前节点的路径表示一个词
*/
int nodeState = 0;
TrieNode(){
count=0;
prefixCount=0;
next=new TrieNode[26];
nodeState = 0;
}
}
}
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
测试类：
package com.xq.algorithm;
import java.util.List;
public class WordTrieMain {
public static void main(String[] args){
test();
}
public static void test1(){
WordTrie trie=new WordTrie();
trie.addWord(\"ibiyzbi\");
System.out.println(\"----------------------------------------\");
List<String> words=trie.searchWord(\"bi\");
for(String s: words){
System.out.println(s);
}
}
public static void test(){
WordTrie trie=new WordTrie();
trie.addWord(\"abi\");
trie.addWord(\"ai\");
trie.addWord(\"aqi\");
trie.addWord(\"biiiyou\");
trie.addWord(\"dqdi\");
trie.addWord(\"ji\");
trie.addWord(\"li\");
trie.addWord(\"liqing\");
trie.addWord(\"liqq\");
trie.addWord(\"liqqq\");
trie.addWord(\"qi\");
trie.addWord(\"qibi\");
trie.addWord(\"i\");
trie.addWord(\"ibiyzbi\");
List<String> list=trie.prefixSearchWord(\"li\");
for(String s: list){
System.out.println(s);
}
System.out.println(\"----------------------------------------\");
List<String> li=trie.searchWord(\"i\");
for(String s: li){
System.out.println(s);
}
System.out.println(\"----------------------------------------\");
List<String> words=trie.searchWord(\"bi\");
for(String s: words){
System.out.println(s);
}
System.out.println(\"----------------------------------------\");
List<String> lst=trie.searchWord(\"q\");
for(String s: lst){
System.out.println(s);
}
}
}
---------------------
作者：Wj要努力
来源：CSDN
原文：https://blog.csdn.net/dreamzuora/article/details/85024052
版权声明：本文为博主原创文章，转载请附上博文链接！
继续阅读与本文标签相同的文章
华为路由简单配置
-
详解安检违禁品识别设计方案
2026-05-18栏目： 教程
-
Pdf转excel的简单方法分享
2026-05-18栏目： 教程
-
人脸识别技术发展如花如荼 未来可期
2026-05-18栏目： 教程
-
MaxCompute开发者夏季颁奖礼~久久感谢有你
2026-05-18栏目： 教程
-
第六届世界互联网大会即将举行 乌镇将试行5G自动微公交
2026-05-18栏目： 教程