java 字典树模版
时间: 2023-11-13 12:56:11 浏览: 46
好的,这里是 Java 实现的字典树模板:
```java
class TrieNode {
private TrieNode[] children;
private boolean isEnd;
public TrieNode() {
children = new TrieNode[26];
isEnd = false;
}
public boolean containsKey(char ch) {
return children[ch - 'a'] != null;
}
public TrieNode get(char ch) {
return children[ch - 'a'];
}
public void put(char ch, TrieNode node) {
children[ch - 'a'] = node;
}
public void setEnd() {
isEnd = true;
}
public boolean isEnd() {
return isEnd;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (!node.containsKey(ch)) {
node.put(ch, new TrieNode());
}
node = node.get(ch);
}
node.setEnd();
}
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd();
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private TrieNode searchPrefix(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
if (node.containsKey(ch)) {
node = node.get(ch);
} else {
return null;
}
}
return node;
}
}
```