字母字典树

LeetCode 相关题目：208. 实现 Trie (前缀树)

type Trie struct {
    tries [26]*Trie
    end   bool
}

func (t *Trie) Insert(word string) {
    p := t
    for i := 0; i < len(word); i++ {
       index := word[i] - 'a'
       if p.tries[index] == nil {
          p.tries[index] = &Trie{}
       }
       p = p.tries[index]
    }
    p.end = true
}

func (t *Trie) Search(word string) bool {
    p := t
    for i := 0; i < len(word); i++ {
       index := word[i] - 'a'
       if p.tries[index] == nil {
          return false
       }
       p = p.tries[index]
    }
    return p.end
}

func (t *Trie) StartsWith(prefix string) bool {
    p := t
    for i := 0; i < len(prefix); i++ {
       index := prefix[i] - 'a'
       if p.tries[index] == nil {
          return false
       }
       p = p.tries[index]
    }
    return true
}

0-1 字典树

type Trie struct {
    tries [2]*Trie
}

func (t *Trie) Put(num int) {
    p := t
    for i := 31; i >= 0; i-- {
       bit := num >> i & 1
       if p.tries[bit] == nil {
          p.tries[bit] = &Trie{}
       }
       p = p.tries[bit]
    }
}

func (t *Trie) MaxXor(num int) (maxXor int) {
    p := t
    for i := 31; i >= 0; i-- {
       bit := num >> i & 1
       if p.tries[1^bit] != nil {
          maxXor |= 1 << i
          p = p.tries[1^bit]
       } else {
          p = p.tries[bit]
       }
    }
    return
}