import (
"fmt"
"sort"
"strconv"
)

 type TrieNode map[byte]TrieNode

func main() {

patterns := []string{"TWLO", "CODE", "HTCH"}
givenStrings := []string{"+17474824380", "+14157088956", "+919810155555", "+15109926333"}
ToMatch := preProcess(patterns)

dict := make(map[string]bool)
for _, str := range givenStrings {
	trie := NewTrie()
	trie.BuildTrie(str)
	for _, tomatch := range ToMatch {
		res := trie.MatchString(tomatch)
		if res == true {
			if _, ok := dict[str]; !ok {
				dict[str] = true
			}

		}

	}
}
res := []string{}
for k := range dict {
	res = append(res, k)
}
sort.Strings(res)
fmt.Println(res)

}
func NewTrie() TrieNode {
return TrieNode{}
}
func (t TrieNode) BuildTrie(str string) {
for j := range str {
	trie := t
	for i := j; i < len(str); i++ {
		letter := str[i]
		if _, ok := trie[letter]; !ok {
			trie[letter] = NewTrie()
		}
		trie = trie[letter]
	}
	trie['*'] = nil
}
}
func (t TrieNode) MatchString(str string) bool {
trie := t

for i := 0; i < len(str); i++ {
	letter := str[i]
	if _, ok := trie[letter]; !ok {
		return false
	}
       trie = trie[letter]
}
return true
}

func preProcess(patterns []string) []string {
var result []string
DtoN := map[string]int{"A": 2, "B": 2, "C": 2, "D": 3, "E": 3, "F": 3, "G": 4, "H": 4, "I": 4, "J": 5, "K": 5, "L": 5, "M": 6, "N": 6, "O": 6, "P": 7, "Q": 7, "R": 7, "S": 7, "T": 8, "U": 8, "V": 8, "W": 9, "X": 9, "Y": 9, "Z": 9}
for _, pattern := range patterns {
	converted := ""
	for i := 0; i < len(pattern); i++ {
		converted += strconv.Itoa(DtoN[string(pattern[i])])
	}
	result = append(result, converted)
}
return result
}