字典树
- 1. 背景和定义
- 2. 功能
- 3. 代码实现
1. 背景和定义
算法导论中，Trie叫做“基数树”。其应用范围不仅和字符串有关，本质上其实是个N叉树。 在N叉树上，如果共父节点的N个子节点是有序的字符序列，构造出来就很像字典树了。
2. 功能
字典树的功能是对很多串进行压缩，压缩方法是合并这些字符串的相同前缀。 具体而言，就是字典树的每个节点都代表一个字符，用从根节点到叶子节点的路径来表示一个字符串。 这样做就压缩了所有模式串，并将大量前缀进行了合并，从而节省了时间。
3. 代码实现
代码语言：javascript复制struct TrieNode {
TrieNode *sons[26];
int flag = 0; // flag == 1表示有该单词（叶子节点）
TrieNode() {
memset(sons, 0, 26 * sizeof(TrieNode*));
}
};
class Trie {
private:
TrieNode* root;
public:
/** Initialize your data structure here. */
Trie() {
root = new TrieNode;
}
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode *cur = root;
int len = (int) word.length();
for (int i = 0; i < len; i ) {
if (!cur->sons[word[i] - 'a']) cur->sons[word[i] - 'a'] = new TrieNode();
cur = cur->sons[word[i] - 'a'];
}
cur->flag = 1;
}
/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode *cur = root;
int len = (int) word.length();
for (int i = 0; i < len; i ) {
if (cur->sons[word[i] - 'a']) cur = cur->sons[word[i] - 'a'];
else return false;
}
if (cur->flag) return true;
else return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
TrieNode *cur = root;
int len = (int) prefix.length();
for (int i = 0; i < len; i ) {
if (cur->sons[prefix[i] - 'a']) cur = cur->sons[prefix[i] - 'a'];
else return false;
}
return true;
}
};
