0208.md

• Trie 实际上就是以字符为节点的树

insert("apple")

^（根节点）->a->p->p->l->e$（e 是终点）

search("app")

^->a
^->a->p
^->a->p->p
结束，p 未标记为结束符，查找失败
startsWith("app") 查找过程相同，但不需要检查结束符，查找成功

insert("app")

^->a->p->p$->l->e$

search("app")，搜索到 p，检查其已标记为结束符，查找成功

insert("apart")

^->a->p->p$->l->e$
      |
      a->r->t$

insert("banana")

^->a->p->p$->l->e$
|     |
|     a->r->t$
|
 ->b->a->n->a->n->a

insert("bad")

^->a->p->p$->l->e$
|     |
|     a->r->t$
|
b->a->n->a->n->a
   |
   d

insert("bed")

^->a->p->p$->l->e$
|     |
|     a->r->t$
|
b->a->n->a->n->a
|  |
|  d
|
e->d

• 实现如下

class Trie {
 public:
  /** Initialize your data structure here. */
  Trie() {}

  /** Inserts a word into the trie. */
  void insert(string word) {
    Trie* t = this;
    for (auto& x : word) {
      if (!t->next[x - 'a']) {
        t->next[x - 'a'] = new Trie;
      }
      t = t->next[x - 'a'];
    }
    t->is_end = true;
  }

  /** Returns if the word is in the trie. */
  bool search(string word) {
    Trie* t = this;
    for (auto& x : word) {
      t = t->next[x - 'a'];
      if (!t) {
        return false;
      }
    }
    return t->is_end;
  }

  /** Returns if there is any word in the trie that starts with the given
   * prefix. */
  bool startsWith(string prefix) {
    Trie* t = this;
    for (auto& x : prefix) {
      t = t->next[x - 'a'];
      if (!t) {
        return false;
      }
    }
    return true;
  }

 private:
  vector<Trie*> next{vector<Trie*>(26)};
  bool is_end = false;
};