字典树

应用场景:

又称“单词查找树”，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

字典树结构

时间复杂度

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熟悉这种方法。