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")
1 true
tm.query("hello there")
false
tm.query("there")
2 true
tm.query("ther")
false
tm.query("the")
3 true
tm.query("")
false