CG_go_009_TrieMap



In [1]:
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
}

In [2]:
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
}

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

In [4]:
tm.query("hello")


1
true

In [5]:
tm.query("hello there")


false

In [6]:
tm.query("there")


2
true

In [7]:
tm.query("ther")


false

In [8]:
tm.query("the")


3
true

In [9]:
tm.query("")


false