题目

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。

这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。

void insert(String word) 向前缀树中插入字符串 word 。

boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。

boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：输入inputs = ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]

inputs = [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

输出[null, null, true, false, true, null, true]

解释 Trie trie = new Trie();

trie.insert("apple");

trie.search("apple"); // 返回 True

trie.search("app"); // 返回 False

trie.startsWith("app"); // 返回 True

trie.insert("app");

trie.search("app"); // 返回 True

提示：1 <= word.length, prefix.length <= 2000

word 和 prefix 仅由小写英文字母组成

insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

注意：本题与主站 208 题相同：

解题思路分析

1、trie树；时间复杂度O(n)，空间复杂度O(n)

type Trie struct {
   next   [26]*Trie
   ending int
}

func Constructor() Trie {
   return Trie{
      next:   [26]*Trie{},
      ending: 0,
   }
}

func (this *Trie) Insert(word string) {
   temp := this
   for _, v := range word {
      value := v - 'a'
      if temp.next[value] == nil {
         temp.next[value] = &Trie{
            next:   [26]*Trie{},
            ending: 0,
         }
      }
      temp = temp.next[value]
   }
   temp.ending++
}

func (this *Trie) Search(word string) bool {
   temp := this
   for _, v := range word {
      value := v - 'a'
      if temp = temp.next[value]; temp == nil {
         return false
      }
   }
   if temp.ending > 0 {
      return true
   }
   return false
}

func (this *Trie) StartsWith(prefix string) bool {
   temp := this
   for _, v := range prefix {
      value := v - 'a'
      if temp = temp.next[value]; temp == nil {
         return false
      }
   }
   return true
}

2、trie树；时间复杂度O(n)，空间复杂度O(n)

type Trie struct {
   next   map[byte]*Trie
   ending int
}

/** Initialize your data structure here. */
func Constructor() Trie {
   return Trie{
      next:   make(map[byte]*Trie),
      ending: 0,
   }
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
   temp := this
   for _, v := range word {
      value := byte(v - 'a')
      if temp.next[value] == nil {
         temp.next[value] = &Trie{
            next:   make(map[byte]*Trie),
            ending: 0,
         }
      }
      temp = temp.next[value]
   }
   temp.ending++
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
   temp := this
   for _, v := range word {
      value := byte(v - 'a')
      if temp = temp.next[value]; temp == nil {
         return false
      }
   }
   if temp.ending > 0 {
      return true
   }
   return false
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
   temp := this
   for _, v := range prefix {
      value := byte(v - 'a')
      if temp = temp.next[value]; temp == nil {
         return false
      }
   }
   return true
}

总结

Medium题目，题目同leetcode 208.实现Trie(前缀树)