数据结构源码
实现类
import java.util.TreeMap;
public class Trie {
private class Node {
public boolean isWord;
public TreeMap<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<>();
}
public Node() {
this(false);
}
}
private Node root;
private int size;
public Trie() {
root = new Node();
size = 0;
}
/**
* 获得Trie中存储的单词数量
* @return
*/
public int getSize() {
return size;
}
/**
* 向Trie中添加一个新的单词word
* @param word
*/
public void add(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
cur.next.put(c, new Node());
}
cur = cur.next.get(c);
}
if (!cur.isWord) {
cur.isWord = true;
size++;
}
}
/**
* 查询单词word是否在Trie中
* @return
*/
public boolean contains(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
return false;
}
cur = cur.next.get(c);
}
return cur.isWord;
}
/**
* 查询是否在Trie中有单词以prefix为前缀
* @param prefix
* @return
*/
public boolean isPrefix(String prefix) {
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (cur.next.get(c) == null) {
return false;
}
cur = cur.next.get(c);
}
return true;
}
public static void main(String[] args) {
}
}
数据结构拆解
维护字段和内部类
private class Node {
public boolean isWord;
public TreeMap<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<>();
}
public Node() {
this(false);
}
}
private Node root;
private int size;
构造函数
public Trie() {
root = new Node();
size = 0;
}
增
/**
* 向Trie中添加一个新的单词word
* @param word
*/
public void add(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
cur.next.put(c, new Node());
}
cur = cur.next.get(c);
}
if (!cur.isWord) {
cur.isWord = true;
size++;
}
}
删
改
查
/**
* 获得Trie中存储的单词数量
* @return
*/
public int getSize() {
return size;
}
/**
* 查询单词word是否在Trie中
* @return
*/
public boolean contains(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
return false;
}
cur = cur.next.get(c);
}
return cur.isWord;
}
/**
* 查询是否在Trie中有单词以prefix为前缀
* @param prefix
* @return
*/
public boolean isPrefix(String prefix) {
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (cur.next.get(c) == null) {
return false;
}
cur = cur.next.get(c);
}
return true;
}