type TrieMap struct {
    node  map[byte]*TrieMap
    empty bool
    value string
}

func (tm *TrieMap) add(key, value string) {
    cur := tm
    for _, c := range []byte(key) {
        if _, ok := cur.node[c]; ! ok {
            cur.node[c] = &TrieMap{make(map[byte]*TrieMap), true, ""}
        }
        cur = cur.node[c]
    }
    cur.empty = false
    cur.value = value
}

func (tm *TrieMap) query(key string) (string, bool) {
    cur := tm
    for _, c := range []byte(key) {
        val, ok := cur.node[c]
        if !ok {
            return "", false
        }
        cur = val
    }
    return cur.value, !cur.empty
}

func NewTrieMap(keys, values []string) *TrieMap {
    tm := &TrieMap{make(map[byte]*TrieMap), true, ""}
    for i, key := range keys {
        tm.add(key, values[i])
    }
    return tm
}

keys := []string{"hello", "there", "the"}
values := []string{"1", "2", "3"}
tm := NewTrieMap(keys, values)

tm.query("hello")

tm.query("hello there")

tm.query("there")

tm.query("ther")

tm.query("the")

tm.query("")