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"));
}
}
上述代码定义了两个类:TrieNode和Trie。TrieNode表示前缀树的节点,其中包含一个children映射用于存储子节点,以及一个isWord标记表示当前节点是否为单词结尾。
Trie类表示前缀树,其中包含一个根节点root,构造函数用于初始化根节点。
Trie类提供了三个方法:
insert(String word) 方法用于将一个单词插入到前缀树中。
search(String word) 方法用于判断一个单词是否存在于前缀树中。
startsWith(String prefix) 方法用于判断是否存在以给定前缀开头的单词。