应用场景:
又称“单词查找树”，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
字典树结构
时间复杂度
O(lgn)
字典树节点
typedef struct Trie_node {
bool exist; /// 标记该结点处是否构成单词
struct Trie_node* next[26]; /// 指向各个子树的指针
Trie_node() : exist(false) {
memset(next, 0, sizeof(Trie_node*)*26);
}
} TrieNode, *Trie;
建树
void buildTrie(Trie root, const vector<string>& dict) {
int index;
for(int j=0; j<dict.size(); ++j) {
Trie p = root;
int i = 0;
for(; i<dict[j].length(); ++i) {
index = dict[j][i]-'a';
if(p->next[index] == NULL)
p->next[index] = new TrieNode();
p = p->next[index];
if(i == dict[j].length()-1)
p->exist = true;
}
}
}
查找过程
string findStr(Trie root, const string& str) {
Trie p = root;
int index;
for(int i=0; i<str.length(); ++i) {
index = str[i]-'a';
if(p->next[index]) {
if(p->next[index]->exist)
return str.substr(0, i+1);
p = p->next[index];
} else
return str;
}
return str;
}
};
总体还是很简单的，可以通过 leetcode648: replace words熟悉这种方法。
