{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "type TrieMap struct {\n", " node map[byte]*TrieMap\n", " empty bool\n", " value string\n", "}\n", "\n", "func (tm *TrieMap) add(key, value string) {\n", " cur := tm\n", " for _, c := range []byte(key) {\n", " if _, ok := cur.node[c]; ! ok {\n", " cur.node[c] = &TrieMap{make(map[byte]*TrieMap), true, \"\"}\n", " }\n", " cur = cur.node[c]\n", " }\n", " cur.empty = false\n", " cur.value = value\n", "}\n", "\n", "func (tm *TrieMap) query(key string) (string, bool) {\n", " cur := tm\n", " for _, c := range []byte(key) {\n", " val, ok := cur.node[c]\n", " if !ok {\n", " return \"\", false\n", " }\n", " cur = val\n", " }\n", " return cur.value, !cur.empty\n", "}" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "func NewTrieMap(keys, values []string) *TrieMap {\n", " tm := &TrieMap{make(map[byte]*TrieMap), true, \"\"}\n", " for i, key := range keys {\n", " tm.add(key, values[i])\n", " }\n", " return tm\n", "}" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "keys := []string{\"hello\", \"there\", \"the\"}\n", "values := []string{\"1\", \"2\", \"3\"}\n", "tm := NewTrieMap(keys, values)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n", "true\n" ] } ], "source": [ "tm.query(\"hello\")" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "false\n" ] } ], "source": [ "tm.query(\"hello there\")" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2\n", "true\n" ] } ], "source": [ "tm.query(\"there\")" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "false\n" ] } ], "source": [ "tm.query(\"ther\")" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n", "true\n" ] } ], "source": [ "tm.query(\"the\")" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "false\n" ] } ], "source": [ "tm.query(\"\")" ] } ], "metadata": { "kernelspec": { "display_name": "Go (lgo)", "language": "go", "name": "lgo" }, "language_info": { "file_extension": "", "mimetype": "", "name": "go", "version": "" } }, "nbformat": 4, "nbformat_minor": 2 }