前缀树

type Trie struct {
	links map[byte]*Trie // 这道题保证了输入的都是小写字母，links也可用大小为26的数组实现
	IsEnd bool
}

func Constructor() Trie {
	return Trie{
		links: map[byte]*Trie{},
	}
}

/** Inserts a word into the trie.

Time complexity : O(m), where m is the key length.

Space complexity : O(m)
In the worst case newly inserted key doesn't share a prefix with the the keys already inserted in the trie.
We have to add m new nodes, which takes us O(m) space.
*/
func (t *Trie) Insert(word string) {
	node := t
	for i := 0; i < len(word); i++ {
		if node.links[word[i]] == nil {
			node.links[word[i]] = &Trie{links: map[byte]*Trie{}}
		}
		node = node.links[word[i]]
	}
	node.IsEnd = true
}

/** Returns if the word is in the trie.

Time complexity : O(m) In each step of the algorithm we search for the next key character.
In the worst case the algorithm performs mm operations.

Space complexity : O(1)
*/
func (t *Trie) Search(word string) bool {
	node := t.search(word)
	return node != nil && node.IsEnd
}

/** Returns if there is any word in the trie that starts with the given prefix.
Time complexity : O(m)

Space complexity : O(1)
*/
func (t *Trie) StartsWith(prefix string) bool {
	return t.search(prefix) != nil
}

func (t *Trie) search(s string) *Trie {
	node := t
	for i := 0; i < len(s); i++ {
		if node.links[s[i]] == nil {
			return nil
		}
		node = node.links[s[i]]
	}
	return node
}

/*
Time complexity : O(m) In each step of the algorithm we search for the next key character.
In the worst case the algorithm performs m operations.

Space complexity : O(1)
*/
func (t *Trie) SearchLongestPrefixOf(word string) string {
	node := t
	i := 0
	for i < len(word) {
		ch := word[i]
		if node.links[ch] == nil || len(node.links) > 1 || node.IsEnd {
			return word[:i]
		}
		node = node.links[ch]
		i++
	}
	return word[:i]
}

type MapSum struct {
	links map[byte]*MapSum
	val   int
	isEnd bool
}

func Constructor1() MapSum {
	return MapSum{links: map[byte]*MapSum{}}
}

func (s *MapSum) Insert(key string, val int) {
	for i := range key {
		if s.links[key[i]] == nil {
			s.links[key[i]] = &MapSum{links: map[byte]*MapSum{}}
		}
		s = s.links[key[i]]
	}
	s.val = val
	s.isEnd = true
}

func (s *MapSum) Sum(prefix string) int {
	for i := range prefix {
		if s.links[prefix[i]] == nil {
			return 0
		}
		s = s.links[prefix[i]]
	}
	result := 0
	var dfs func(t *MapSum)
	dfs = func(t *MapSum) {
		if t.isEnd {
			result += t.val
		}
		for _, v := range t.links {
			dfs(v)
		}
	}
	dfs(s)
	return result
}

func replaceWords(dict []string, sentence string) string {
	trie := &Trie{links: map[byte]*Trie{}}
	for _, v := range dict {
		trie.Insert(v)
	}
	result := strings.Split(sentence, " ")
	for i, v := range result {
		p := trie.SearchBreifPrifix(v)
		if p != "" {
			result[i] = p
		}
	}
	return strings.Join(result, " ")
}

func (t *Trie) SearchBreifPrifix(word string) string {
	i := 0
	for i < len(word) {
		if t.IsEnd || t.links[word[i]] == nil {
			break
		}
		t = t.links[word[i]]
		i++
	}
	if t.IsEnd {
		return word[:i]
	}
	return ""
}

type WordDictionary struct {
	links map[byte]*WordDictionary
	isEnd bool
}

func Constructor2() WordDictionary {
	return WordDictionary{
		links: map[byte]*WordDictionary{},
	}
}

func (d *WordDictionary) AddWord(word string) {
	for i := range word {
		if d.links[word[i]] == nil {
			d.links[word[i]] = &WordDictionary{links: map[byte]*WordDictionary{}}
		}
		d = d.links[word[i]]
	}
	d.isEnd = true
}

func (d *WordDictionary) Search(word string) bool {
	if len(word) == 0 {
		return d.isEnd
	}
	if len(d.links) == 0 || word[0] != '.' && d.links[word[0]] == nil {
		return false
	}
	if word[0] == '.' {
		for _, v := range d.links {
			if v.Search(word[1:]) {
				return true
			}
		}
		return false
	}
	d = d.links[word[0]]
	return d.Search(word[1:])
}

func findWords(board [][]byte, words []string) []string {
	if len(board) == 0 || len(board[0]) == 0 || len(words) == 0 {
		return nil
	}
	m, n := len(board), len(board[0])
	trie := &Trie{links: make(map[byte]*Trie, 0)}
	for _, v := range words {
		trie.Insert(v)
	}
	set := make(map[string]struct{}, 0)
	var path []byte
	dirs := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	var dfs func(t *Trie, r, c int, seen [][]bool)
	dfs = func(t *Trie, r, c int, seen [][]bool) {
		if r < 0 || r >= m || c < 0 || c >= n || seen[r][c] {
			return
		}
		ch := board[r][c]
		if t.links[ch] == nil {
			return
		}
		path = append(path, ch)
		seen[r][c] = true
		if t.links[ch].IsEnd {
			set[string(path)] = struct{}{}
		}
		for _, d := range dirs {
			dfs(t.links[ch], r+d[0], c+d[1], seen)
		}
		// 回溯
		path = path[:len(path)-1]
		seen[r][c] = false
	}
	for r := range board {
		for c := range board[r] {
			dfs(trie, r, c, genSeen(m, n))
		}
	}
	result := make([]string, 0, len(set))
	for k := range set {
		result = append(result, k)
	}
	return result
}

func genSeen(m, n int) [][]bool {
	r := make([][]bool, m)
	for i := range r {
		r[i] = make([]bool, n)
	}
	return r
}