数据结构——Trie树
概念
Trie树,又称字典树、前缀树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
Trie树的结构如下图所示:
Trie树中的节点数据结构如下:
- 当前字符
- 子节点数组(如果全为小写字母的话,子节点数量固定为26个,根据字符来确定在数组中的位置,如'a'的下标为0,'z'为25)
- 是否为一个单词的结尾(标红的节点)
- 出现次数
特点:root节点不存储字符。
代码实现
public class Trie {
private Node root;
class Node{
int count;
char ch;
Node[] child;
boolean isEnd;
public Node() {
this.count = 1;
this.child = new Node[26];
this.isEnd = false;
}
}
/** Initialize your data structure here. */
public Trie() {
this.root = new Node();
}
/** Inserts a word into the trie. */
public void insert(String word) {
if (null == word || "".equals(word)) return;
if (this.search(word)) return;
Node cur = this.root;
char[] chars = word.toCharArray();
for(char c : chars) {
//根据字符找到在子节点数组中的下标
int pos = c - 'a';
Node child = cur.child[pos];
//如果子节点没有被初始化过则初始化,并设置其字符
if (child == null) {
cur.child[pos] = new Node();
cur.child[pos].ch = c;
}
cur.count++;
//更新cur节点为子节点,向下递归
cur = cur.child[pos];
}
//最后一个字符的节点
cur.isEnd = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
if (null == word || "".equals(word)) return true;
Node cur = this.root;
char[] chars = word.toCharArray();
for (char c : chars) {
int pos = c - 'a';
Node node = cur.child[pos];
if (node == null) return false;
cur = node;
}
return cur.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
if (null == prefix || "".equals(prefix)) return true;
Node cur = this.root;
char[] chars = prefix.toCharArray();
for (char c : chars) {
int pos = c - 'a';
Node node = cur.child[pos];
if (node == null) return false;
cur = node;
}
return cur.count > 0;
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("a");
trie.insert("adc");
trie.insert("aer");
System.out.println(trie.search("a"));
System.out.println(trie.startsWith("a"));
}
}
结果:
208. Implement Trie (Prefix Tree)
超过94%,感觉还不错~