字典树

通常用于查找字符串，比如在搜索框中搜索会自动提示，或者lucene
常用操作有 插入和查找, 删除

代码

习题 208. Implement Trie (Prefix Tree)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public static class TrieNode {
	char val;
	TrieNode[] children;
	boolean leaf;
	// Initialize your data structure here.
	public TrieNode() {
		this.children = new TrieNode[26];
		leaf = false;
	}
	public TrieNode(char c) {
		this.val = c;
		children = new TrieNode[26];
		leaf = false;
	}
}
public static class Trie {
	private TrieNode root;
	public Trie() {
		root = new TrieNode();
	}
	// Inserts a word into the trie.
	public void insert(String word) {
		TrieNode cur = root;
		for (int i = 0; i < word.length(); i++) {
			int index = word.charAt(i) - 'a';
			TrieNode tmp = cur.children[index];
			if (tmp == null) {
				tmp = new TrieNode(word.charAt(i));
				cur.children[index] = tmp;
			}
			if (i == word.length() - 1) {
				tmp.leaf = true;
			}
			cur = tmp;
		}
	}
	// Returns if the word is in the trie.
	public boolean search(String word) {
		TrieNode cur = root;
		for (int i = 0; i < word.length(); i++) {
			int index = word.charAt(i) - 'a';
			TrieNode tmp = cur.children[index];
			if (tmp != null) {
				if (i == word.length() - 1 && tmp.leaf) {
					return true;
				}
				cur = tmp;
			} else {
				// 无此节点
				return false;
			}
		}
		return false;
	}
	// Returns if there is any word in the trie
	// that starts with the given prefix.
	public boolean startsWith(String prefix) {
		TrieNode cur = root;
		for (int i = 0; i < prefix.length(); i++) {
			int index = prefix.charAt(i) - 'a';
			TrieNode tmp = cur.children[index];
			if (tmp != null) {
				cur = tmp;
			} else {
				// 无此节点
				return false;
			}
		}
		//prefix是该字符串也可以
		return true;
	}
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");