📑 题目：208. 实现 Trie (前缀树)

中等 🕓 2021-09-08 📈 频次： 15

**

🚀 本题 LeetCode 传送门

题目大意

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

解题思路

  • 要求实现一个 Trie 的数据结构，具有 insert, search, startsWith 三种操作
  • 这一题就是经典的 Trie 实现。本题的实现可以作为 Trie 的模板。

代码

  1. package leetcode
  3. type Trie struct {
  4.  isWord   bool
  5.  children map[rune]*Trie
  6. }
  8. /** Initialize your data structure here. */
  9. func Constructor208() Trie {
  10.  return Trie{isWord: false, children: make(map[rune]*Trie)}
  11. }
  13. /** Inserts a word into the trie. */
  14. func (this *Trie) Insert(word string) {
  15.  parent := this
  16.  for _, ch := range word {
  17.   if child, ok := parent.children[ch]; ok {
  18.    parent = child
  19.   } else {
  20.    newChild := &Trie{children: make(map[rune]*Trie)}
  21.    parent.children[ch] = newChild
  22.    parent = newChild
  23.   }
  24.  }
  25.  parent.isWord = true
  26. }
  28. /** Returns if the word is in the trie. */
  29. func (this *Trie) Search(word string) bool {
  30.  parent := this
  31.  for _, ch := range word {
  32.   if child, ok := parent.children[ch]; ok {
  33.    parent = child
  34.    continue
  35.   }
  36.   return false
  37.  }
  38.  return parent.isWord
  39. }
  41. /** Returns if there is any word in the trie that starts with the given prefix. */
  42. func (this *Trie) StartsWith(prefix string) bool {
  43.  parent := this
  44.  for _, ch := range prefix {
  45.   if child, ok := parent.children[ch]; ok {
  46.    parent = child
  47.    continue
  48.   }
  49.   return false
  50.  }
  51.  return true
  52. }
  54. /**
  55.  * Your Trie object will be instantiated and called as such:
  56.  * obj := Constructor();
  57.  * obj.Insert(word);
  58.  * param_2 := obj.Search(word);
  59.  * param_3 := obj.StartsWith(prefix);
  60.  */