前缀树

struct TrieNode {
  array<TrieNode *, 26> children;
  bool isEnd;
 
  TrieNode() : isEnd(false) {
    for (int i = 0; i < 26; i++) {
      children[i] = nullptr;
    }
  }
};
 
class Trie {
public:
  Trie() { root = new TrieNode(); }
 
  void insert(std::string word) {
    auto node = root;
    for (auto &c : word) {
      int idx = c - 'a';
      if (node->children[idx] == nullptr) {
        node->children[idx] = new TrieNode();
      }
      node = node->children[idx];
    }
    node->isEnd = true;
  }
 
  bool search(std::string word) {
    auto node = root;
    for (auto &c : word) {
      int idx = c - 'a';
      if (node->children[idx] == nullptr) {
        return false;
      }
      node = node->children[idx];
    }
    return node->isEnd;
  }
 
  bool startsWith(std::string prefix) {
    auto node = root;
    for (auto &c : prefix) {
      int idx = c - 'a';
      if (node->children[idx] == nullptr) {
        return false;
      }
      node = node->children[idx];
    }
    return true;
  }
 
private:
  TrieNode *root;
};