type trie struct {
	word bool
	next [26]*trie
}

func (t *trie) insert(s string) {
	for _, r := range s {
		i := r - 'a'
		if t.next[i] == nil {
			t.next[i] = &trie{}
		}
		t = t.next[i]
	}
	t.word = true
}

func (t *trie) search(s string) *trie {
	res := t
	for _, r := range s {
		res = res.next[r-'a']
		if res == nil {
			break
		}
	}
	return res
}

type MagicDictionary struct {
	tree trie
}

/** Initialize your data structure here. */
func Constructor() MagicDictionary {
	return MagicDictionary{}
}

/** Build a dictionary through a list of words */
func (this *MagicDictionary) BuildDict(dict []string) {
	for _, s := range dict {
		this.tree.insert(s)
	}
}

/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
func (this *MagicDictionary) Search(word string) bool {
	for i := range word {
		t := this.tree.search(word[:i])
		if t == nil {
			continue
		}
		for j := 0; j < 26; j++ {
			if j == int(word[i]-'a') || t.next[j] == nil {
				continue
			}
			if s := t.next[j].search(word[i+1:]); s != nil && s.word {
				return true
			}
		}
	}
	return false
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.BuildDict(dict);
 * param_2 := obj.Search(word);
 */