（15）Go实现trie-字典树/前缀树

下面用2种分别用map和数组实现字典树：

（方法1）map实现，用map实现的方法意义不大，还不如直接用map，主要是实现方法里面
分为非递归和递归两种算法
type trieNode struct {
    isWord bool  // 是否是单词结尾
    next   map[rune]*trieNode
}

type trie struct {
    size int  // 节点数量
    root *trieNode
}

func NewTrie() *trie {
    return &trie{
        0,
        &trieNode{false, make(map[rune]*trieNode)},
    }
}

func (this *trie) GetSize() int {
    return this.size
}

// 非递归算法
func (this *trie) Add(word string) {
    if len(word) == 0 {
        return
    }

    cur := this.root
    for _, v := range word {
        _, ok := cur.next[v] // 在NewTrie中已经初始化，能直接用
        if !ok {
            cur.next[v] = &trieNode{false, map[rune]*trieNode{}}
        }
        cur = cur.next[v]
    }
    // 判断该单词之前是否已经添加到tree中了
    if !cur.isWord {
        cur.isWord = true
        this.size++
    }
}

// 递归算法
func (this *trie) Add2(word string) {
    if len(word) == 0 {
        return
    }
    cur := this.root
    this.size = this.size + cur.insert(word)
}

// 辅助完成递归函数:在node节点中插入word,如果是已经存在的单词,返回0,如果不存在返回1
func (node *trieNode) insert(word string) int {
    _, ok := node.next[rune(word[0])]
    if !ok {
        node.next[rune(word[0])] = &trieNode{false,
            map[rune]*trieNode{}}
    }
    node = node.next[rune(word[0])]

    if len(word) == 1 {
        if !node.isWord {
            node.isWord = true
            return 1
        }
        return 0
    }

    return node.insert(word[1:])
}

// 查询是否包含某个单词
func (this *trie) Contains(word string) bool {
    if len(word) == 0 {
        return false
    }

    cur := this.root
    for _, v := range word {
        t1, ok := cur.next[v]
        if !ok {
            return false
        }
        cur = t1
    }
    return cur.isWord
}

// 前缀是否有以prefix为前缀的单词
func (this *trie) IsPrefix(word string) bool {
    if len(word) == 0 {
        return false
    }

    cur := this.root
    for _, v := range word {
        t1, ok := cur.next[v]
        if !ok {
            return false
        }
        cur = t1
    }
    return true
}

（方法2）用数组实现字典树
type trie struct {
    size   int
    isWord bool
    // 只支持26个小写字母或大写字母,根据实际情做改变况而定
    next [26]*trie
}

func NewTrie() *trie {
    return new(trie)
}

func (this *trie) Insert(word string) {
    if len(word) == 0 {
        return
    }

    cur := this
    for i, _ := range word {
        if cur.next[word[i]-'a'] == nil {
            cur.next[word[i]-'a'] = new(trie)
        }
        cur = cur.next[word[i]-'a']
    }
    if !cur.isWord {
        cur.isWord = true
        cur.size++
    }
}

// 是否包含某个单词
func (this *trie) Contains(word string) bool {
    length := len(word)
    if length == 0 {
        return false
    }

    cur := this
    for i := 0; i < length; i++ {
        if cur = cur.next[i]; cur == nil {
            return false
        }
    }
    return cur.isWord
}

// 是否包含preWith前缀的单词
func (this *trie) IsPrefix(preWith string) bool {
    length := len(preWith)
    if length == 0 {
        return true
    }

    cur := this
    for i := 0; i < length; i++ {
        if cur := cur.next[i]; cur == nil {
            return false
        }
    }
    return true
}

相关：
1）trie解决leetcode-207：实现trie
https://www.jianshu.com/p/d95153f382f6
2）trie解决leetcode-211：添加与搜索单词
https://www.jianshu.com/p/74103f51aa36
3）trie解决leetcode-677：键值映射
https://www.jianshu.com/p/dd247d5591a2

有bug欢迎指出，转载请注明出处。