import java.util.*;
class TrieNode {
private Map<Character, TrieNode> children;
private boolean isWord;
public TrieNode() {
children = new HashMap<>();
isWord = false;
}
public Map<Character, TrieNode> getChildren() {
return children;
}
public boolean isWord() {
return isWord;
}
public void setWord(boolean word) {
isWord = word;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node.getChildren().computeIfAbsent(c, k -> new TrieNode());
node = node.getChildren().get(c);
}
node.setWord(true);
}
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isWord();
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private TrieNode searchPrefix(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (!node.getChildren().containsKey(c)) {
return null;
}
node = node.getChildren().get(c);
}
return node;
}
}
public class Test {
public static void main(String[] args) {
Trie t = new Trie();
t.insert("ab");
t.insert("acjmn");
t.insert("adg");
t.insert("adk");
System.out.println(t.search("acj"));
System.out.println(t.search("acjmn"));
System.out.println(t.startsWith("acj"));
}
}
上述代碼定義了兩個(gè)類：TrieNode和Trie忽洛。TrieNode表示前綴樹的節(jié)點(diǎn)绘面，其中包含一個(gè)children映射用于存儲(chǔ)子節(jié)點(diǎn)欺税，以及一個(gè)isWord標(biāo)記表示當(dāng)前節(jié)點(diǎn)是否為單詞結(jié)尾侈沪。
Trie類表示前綴樹，其中包含一個(gè)根節(jié)點(diǎn)root晚凿，構(gòu)造函數(shù)用于初始化根節(jié)點(diǎn)亭罪。
Trie類提供了三個(gè)方法：
insert(String word) 方法用于將一個(gè)單詞插入到前綴樹中。
search(String word) 方法用于判斷一個(gè)單詞是否存在于前綴樹中歼秽。
startsWith(String prefix) 方法用于判斷是否存在以給定前綴開頭的單詞应役。
