【结构】【c++】字典树trie，前缀树

字典树的每个节点有以下字段

1. 指向子节点的指针数组children
2. bool值isEnd，表示该节点是否可以为string的结尾

#include 

using namespace std;

class Trie {
private:
  vector children;
  bool isEnd;
  Trie* searchPrefix(string prefix) {
    Trie* node = this;
    for (auto&& ch : prefix) {
      ch -= 'a';
      if (node->children[ch] == nullptr) {
        return nullptr;
      }
      node = node->children[ch];
    }
    return node;
  }

public:
  // why children can be inited like this
  Trie() : isEnd(false), children(26) {}
  void insert(string word) {
    Trie* node = this;
    for (auto&& ch : word) {
      ch -= 'a';
      if (node->children[ch] = nullptr) {
        node->children[ch] = new Trie();
      }
      node = node->children[ch];
    }
    node->isEnd = true;
  }
  bool search(string word) {
    Trie* node = this->searchPrefix(word);
    return node != nullptr && node->isEnd;
  }
  bool startsWith(string word) {
    return this->searchPrefix(word) != nullptr;
  }
};

在工程领域中 Trie 的应用面不广。

至于一些诸如「联想输入」、「模糊匹配」、「全文检索」的典型场景在工程主要是通过 ES (ElasticSearch) 解决的。

而 ES 的实现则主要是依靠「倒排索引」