208.M 实现 Trie (前缀树)

Problem: 208. 实现 Trie (前缀树)

思路

首先定义Trie结构体，用长度为26的数组来表示子节点，然后下标为0的位置表示字母a，下标为1的位置表示字母b，依此类推；再用isEnd表示节点是否为叶子节点。

Code

type Trie struct {
	children [26]*Trie //长度为26的数组，方便后续写入数据
	isEnd    bool
}

func Constructor() Trie {
	return Trie{}
}

func (t *Trie) Insert(word string) {
	cur := t
	for _, ch := range word {
		index := ch - 'a'
		if cur.children[index] == nil {
			cur.children[index] = &Trie{}
		}
		cur = cur.children[index]
	}
	cur.isEnd = true
}

func (t *Trie) Search(word string) bool {
	if len(word) == 0 {
		return false
	}

	node := t.searchPrefix(word)
	return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
	return t.searchPrefix(prefix) != nil
}

func (t *Trie) searchPrefix(prefix string) *Trie {
	cur := t
	for _, ch := range prefix {
		index := ch - 'a'
		if cur.children[index] == nil {
			return nil
		}
		cur = cur.children[index]
	}
	return cur
}