也称前缀树或Trie树，用于高效存储和检索指定的字符串或字符串前缀是否存在于指定的字符串集合中。字典树一般用于搜索词自动补全或拼写提示。通过在树结点中附加出现次数的信息，也可以用于统计词频，比如给出前缀，返回前5个搜索最频繁的搜索词。

字典树的三个基本性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

字典树支持以下操作：

  1. void insert(string word)：插入字符串word。
  2. bool search(string word)：返回字符串word是否存在于前缀树中。
  3. bool startWith(string prefix)：返回指定的前缀是否存在于前缀树中。
  4. vector<string> listStartWith(string prefix)：返回指定前缀的全部字符串。这个接口也可以设计成返回出现次数最多的前n个字符串。

以下是一个精简版的字典树的模板：

class Trie {
private:
    int nxt[100000][26] = {0}; // 使用数组来保存树结构，最大支持100000个结点
	int cnt = 0;
    bool exist[100000] = {0};

public:
    Trie() {}
    
    void insert(string word) {
        int p = 0;
        for(auto ch : word) {
            ch -= 'a';
            if(!nxt[p][ch]) {
                nxt[p][ch] = ++cnt;
            }
            p = nxt[p][ch];
        }
        exist[p] = 1;
    }

    bool search(string word) {
        int p = 0;
        for(auto ch : word) {
            ch -= 'a';
            if(!nxt[p][ch]) {
                return false;
            }
            p = nxt[p][ch];
        }
        return exist[p];
    }

    bool startsWith(string prefix) {
        int p = 0;
        for(auto ch : prefix) {
            ch -= 'a';
            if(!nxt[p][ch]) {
                return false;
            }
            p = nxt[p][ch];
        }
        return true;
    }
};


例题：

  • 无标签