sw Yoo

sw Yoo

No sweat, no sweet

In [1]: 
1
2
3

from collections import deque, defaultdict
from treelib import Tree
from pprint import pprint

Trie

Suppose that

  • Input size $n$
  • length of longest string $m$
Functions Time Complexity
build $O(mn)$
insert $O(m)$
search $O(m)$
delete $O(m)$

panalty : storage requirements

특이사항:

  • root 필요
  • isEnd flag 필요
In [2]: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Node:
    def __init__(self, identifier=None):
        self.identifier = identifier
        self.children = {}
        self.isEnd = False


class Trie:
    def __init__(self):
        self.root = Node(identifier='root')

    def insert(self, x: str):
        """ insert a string x into trie by creating a path from root to End.
        Note that isEnd is marking of a word exist in the trie.
        Args:
            x is a string. """
        cur = self.root
        for i in range(len(x)):
            if x[i] not in cur.children:
                cur.children[x[i]] = Node(identifier=x[i])
            cur = cur.children[x[i]]
        cur.isEnd = True

    def search(self, x: str):
        """ returns True if x presents else False
        Note that x[:] should be matched with a path from root to End.
        Args:
            x is a string. """
        cur = self.root
        for i in range(len(x)):
            if x[i] not in cur.children:
                return False
            cur = cur.children[x[i]]
        return cur != self.root and cur.isEnd

    def show(self):
        s = self.root
        queue = deque([s])
        tree = Tree()
        tree.create_node(tag='root', identifier=s)
        par = {}
        while queue:
            u = queue.popleft()
            for v in u.children.values():
                queue.append(v)
                tree.create_node(tag=v.identifier,
                                 identifier=v,
                                 parent=u)
        tree.show()
In [3]: 
1
2
3
4
5

t = Trie()
keys = ["the", "a", "there", "answer", "any", "bye", "their"]
for key in keys:
    t.insert(key)
t.show()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

root
├── a
│   └── n
│       ├── s
│       │   └── w
│       │       └── e
│       │           └── r
│       └── y
├── b
│   └── y
│       └── e
└── t
    └── h
        └── e
            ├── i
            │   └── r
            └── r
                └── e
In [4]: 
1
2
3
4
5

output = ["Not present in trie", "Present in trie"]
print("{:<7} ---- {}".format("the", output[t.search("the")]))
print("{:<7} ---- {}".format("these", output[t.search("these")]))
print("{:<7} ---- {}".format("their", output[t.search("their")]))
print("{:<7} ---- {}".format("thaw", output[t.search("thaw")]))

1
2
3
4
5

the     ---- Present in trie
these   ---- Not present in trie
their   ---- Present in trie
thaw    ---- Not present in trie

Delete

In [5]: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

class Node:
    def __init__(self, identifier=None):
        self.identifier = identifier
        self.children = {}
        self.isEnd = False


class Trie:
    def __init__(self):
        self.root = Node(identifier='root')

    def insert(self, x: str):
        """ insert a string x into trie by creating a path from root to End.
        Note that isEnd is marking of a word exist in the trie.
        Args:
            x is a string. """
        cur = self.root
        for i in range(len(x)):
            if x[i] not in cur.children:
                cur.children[x[i]] = Node(identifier=x[i])
            cur = cur.children[x[i]]
        cur.isEnd = True

    def search(self, x: str):
        """ returns True if x presents else False
        Note that x[:] should be matched with a path from root to End.
        Args:
            x is a string. """
        cur = self.root
        for i in range(len(x)):
            if x[i] not in cur.children:
                return False
            cur = cur.children[x[i]]
        return cur != self.root and cur.isEnd
    
    def delete(self, x: str):
        """ delete a string x in trie.
        Args:
        :x: a string to delete. """

        def _delete(cur: Node, j: int = 0):
            """ recursively delete and update nodes. 
            returns isSkip flag, which determines a node is deleted or not at finishing time. """
            if j == len(x):
                cur.isEnd = False
                return bool(cur.children)  # True if cur has any child else False
            c = x[j]
            if c not in cur.children:
                print("'{}' is not present".format(x))
                return True
            isSkip = _delete(cur.children[c], j + 1)  # determine delete this node or not.
            if isSkip:
                return True
            cur.children.pop(c)
            return bool(cur.children) or cur.isEnd

        _delete(cur=self.root)
    
    def show(self):
        s = self.root
        queue = deque([s])
        tree = Tree()
        tree.create_node(tag='root', identifier=s)
        while queue:
            u = queue.popleft()
            for v in u.children.values():
                queue.append(v)
                tree.create_node(tag=v.identifier,
                                 identifier=v,
                                 parent=u)
        tree.show()
In [6]: 
1
2
3
4
5
6
7

t = Trie()
keys = ["the", "a", "there", "answer", "any", "bye", "their"]

for key in keys:
    t.insert(key)

t.show()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

root
├── a
│   └── n
│       ├── s
│       │   └── w
│       │       └── e
│       │           └── r
│       └── y
├── b
│   └── y
│       └── e
└── t
    └── h
        └── e
            ├── i
            │   └── r
            └── r
                └── e

delete 이 좀 복잡한데, 설명에 앞서 주의사항은 다음과 같다. (예제는 위의 trie를 바탕으로 설명.)

  • 어떤 string x를 지울때 관련있는 모든 node를 지우면 안된다.
    • e.g., delete(their) $\rightarrow $ their.

그렇다면, 어떻게 구현할 수 있을까? 다음과 같이 구현.

  • dfs 방식으로 탐색하고, finishing time에서 지운다.
    • 이때, children이 하나라도 있거나 isEnd flag가 True인 노드는 지우면 안된다.
    • isSkip Flag를 사용하여 finish time에 노드를 지울지 말지 결정한다.
  • 지워야할 string에 대해서 trie에 모든 character가 존재해야한다.
    • [2]를보면 탐색하다가 child가 없으면 True를 return 한다.
  • recursive하게 지워 나갈때, children이 있는 node는 지우면 안된다. (다른 string들)
  • 한번 delete이 True를 return하면 그 상위 recursive call 들에 대해서는 모두 True가 된다.

정리하여 [1-5]에 대해 예제와 주석으로 설명하겠다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def _delete(cur: Node, j: int = 0):
    """ recursively delete and update nodes. 
    returns isSkip flag, which determines a node is deleted or not at finishing time. """
    if j == len(x):  # [1] dummy depth, string의 모든 charater들이 Trie에 존재하면 `x[:]`path를 따라서 이곳까지 오게 됨.
        cur.isEnd = False  # 삭제되야할 정보기 때문에 search가 되지 않도록 isEnd flag를 False로 만듦.
        return bool(cur.children)  # True if cur has any child else False 
    c = x[j]  
    if c not in cur.children:  # [2] 없는 character가 string x에 있고, 그것에 대해 삭제 명령을 하는 경우. 
        print("'{}' is not present".format(x)) 
        return True # True를 return하므로써 상위 노드들에 대한 delete call의 결과값인 isSkip가 True가 된다.
    isSkip = _delete(cur.children[c], j + 1)  # determine delete this node or not.
    if isSkip:  # [2]
        return True
    cur.children.pop(c)  # [3] isSkip이 False인 노드들은 삭제한다. 
    return bool(cur.children) or cur.isEnd  # [4] children이 하나라도 있거나 isEnd flag가 True인 노드는 지우면 안되므로 이때는 True

아래 [1]부분에 대한 예제는 다음과 같다.
anyway를 추가하였고, any를 삭제했다.
any를 삭제할때 any의 'y' 의 isEnd flag는 False가 되었지만, child 'w'가 존재하기 때문에 삭제하면 안된다.
(any의 'y' 의 isEnd flag는 False가 되었기 때문에 search("any")를 해도 찾을 수 없다.)

1
2
3

if j == len(x):  # [1] dummy depth, string의 모든 charater들이 Trie에 존재하면 `x[:]`path를 따라서 이곳까지 오게 됨.
    cur.isEnd = False  # 삭제되야할 정보기 때문에 search가 되지 않도록 isEnd flag를 False로 만듦.
    return bool(cur.children)  # True if cur has any child else False
In [7]: 
1
2
3
4

t.insert("anyway")
t.delete("any")
t.show()
print("{:<7} ---- {}".format("any", output[t.search("any")]))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

root
├── a
│   └── n
│       ├── s
│       │   └── w
│       │       └── e
│       │           └── r
│       └── y
│           └── w
│               └── a
│                   └── y
├── b
│   └── y
│       └── e
└── t
    └── h
        └── e
            ├── i
            │   └── r
            └── r
                └── e

any     ---- Not present in trie

이어서 [2]에 대한 설명은 다음과 같다. "anywhere"를 검색하면, anyw까지는 trie를 따라가다가 h에서 child가 존재하지 않는다.
따라서 True를 return하므로써 상위 노드들 anyw에 대해 모두 True를 return하게 된다.
그 말은 즉슨 anyw노드들이 finish 될때, isSkip flag가 True여서 삭제하는 상황을 회피하게 된다. 

1
2
3

if c not in cur.children:  # [2] 
    print("'{}' is not present".format(x))
    return True
In [8]: 
1
2

t.delete("anywhere")
t.show()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

'anywhere' is not present
root
├── a
│   └── n
│       ├── s
│       │   └── w
│       │       └── e
│       │           └── r
│       └── y
│           └── w
│               └── a
│                   └── y
├── b
│   └── y
│       └── e
└── t
    └── h
        └── e
            ├── i
            │   └── r
            └── r
                └── e

[2-4] 에 대한 설명은 다음과 같다.
children이 하나라도 있거나 isEnd flag가 True인 노드는 지우면 안되므로 이때는 True
예제는 다음과 같다.
any를 추가하면 y 의 isEnd 가 True가 된다.
따라서, anyway를 지웠을때, 거꾸로 y부터a까지 올라오면서
-way 부분만 지워질 것이고, any의 y에 대한 delete 함수가 finish 될때, isEnd가 True이므로
isSkip flag가 True가 되면서 any는 삭제되지 않는다.

1
2
3
4

    if isSkip:  # [2]
        return True
    cur.children.pop(c)  # [3] isSkip이 False인 노드들은 삭제한다. 
    return bool(cur.children) or cur.isEnd
In [9]: 
1
2
3

t.insert("any")
t.delete("anyway")
t.show()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

root
├── a
│   └── n
│       ├── s
│       │   └── w
│       │       └── e
│       │           └── r
│       └── y
├── b
│   └── y
│       └── e
└── t
    └── h
        └── e
            ├── i
            │   └── r
            └── r
                └── e

또 다른 예제로는 their을 삭제할때,
the의 e에서 delete 함수가 끝날때, e에 대한 child로 r가 존재하므로
isSkip flag가 True가 되면서, the 는 지워지지 않는다.

In [10]: 
1
2

t.delete("their")
t.show()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

root
├── a
│   └── n
│       ├── s
│       │   └── w
│       │       └── e
│       │           └── r
│       └── y
├── b
│   └── y
│       └── e
└── t
    └── h
        └── e
            └── r
                └── e

Practice

leetcode 1 leetcode 2

1. 720. Longest Word in Dictionary

Find the longest word in words that can be built one character at a time by other words in words.

let words be $n$, longest length of word in words be $m$, which is constant.
In [11]: 
1

words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]

Naive

the algorithm needs 2 steps.

  • sort by lexicographical order.
  • incrementally find longest word that can be build one character at a time by oter words in words.
    • check if there is prefix before using words_set

2 overhead exists.

  • preprocessing time takes $O(nlogn)$
  • at worst case, words_set store all word in words and find a word, which takes $O(n)$ for each iteration.
\[O(n^2) \because \text{words_set has at most } n \text{ elements}\]
In [12]: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution(object):
    def longestWord(self, words):
        """ returns longest word
        that can be built one character at a time by other words in words. """
        words = sorted(words)  # sort by lexicographical order.
        words_set, ans = set(['']), ''
        for word in words:
            if word[:-1] in words_set:
                words_set.add(word)
                if len(word) > len(ans):
                    ans = word
        return ans
    
sol = Solution()
print("answer:", sol.longestWord(words))

1
2

answer: apple

Use Trie

consider Trie before we implemented. using dfs search, we can find the longest word in words that satisfies given rules.

design dfs

  • returns longest words among strings that pass a cur node for each dfs recursion(finishing time).
  • search only nodes that isEnd flag is True.
  • update res(follows given rules)
    • e.g.1., banana에서 prefix인 b은 isEnd가 False여서 pruning된다(dfs 탐색에서 제외).
    • e.g.2., apple 에서 l 노드의 경우 isEnd 가 True여서 search 가능하다.
      • app까지가 prefix로 search 해왔을 것이다.
      • recursion을 통해 기존 prefix보다 긴 apple, apply 두가지 longest word가 존재
      • lexical order가 더 작은 apple로 update한다. 
        1

           elif len(loc) == len(res) and loc < res:
    • e.g.3., apply에서 app단계에서의 dfs recursion을 가정해보자.
      • prefix로 ap까지는 탐색하여 구해놓고,
      • app에서 마지막 p는 isEnd가 True이므로 탐색하여 구한 apple로 업데이트한다. 
        1
2
3
4

          loc = dfs(child, prefix + c)
  if len(loc) > len(res):
  # update result, which is longest word that satisfies constraints.
  res = loc
\[O(n)\]
In [13]: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution(object):
    def longestWord(self, words):
        """ returns longest word using trie.
        """
        t = Trie()
        for w in words:
            t.insert(w)
        t.show()

        def dfs(cur: Node, prefix: str = ''):
            """ for each dfs recursion(finishing time),
            returns longest words among strings that pass a cur node. """
            res = prefix
            for c, child in cur.children.items():
                if child.isEnd:
                    loc = dfs(child, prefix + c)
                    if len(loc) > len(res):
                        # update result, which is longest word that satisfies constraints.
                        res = loc
                    elif len(loc) == len(res) and loc < res:
                        # if length is same, comply the smallest lexicographical order.
                        res = loc
            return res

        ans = dfs(t.root, prefix='')
        return ans


t = Trie()
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]

sol = Solution()
print("answer:", sol.longestWord(words))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

root
├── a
│   └── p
│       └── p
│           └── l
│               ├── e
│               └── y
└── b
    └── a
        └── n
            └── a
                └── n
                    └── a

answer: apple

2. 648. Replace Words

Trie를 defaultdict 로 구현하는 trick 이 있다. 좋은 구현 discuss

1

_root = lambda: collections.defaultdict(_root)

이렇게 하면, _root() 의 return 값은 {lambda 함수: {}}가 되어 node를 생성하는데 사용할 수 있다.

1

root = _root

만약 child node를 추가하고싶으면, 

1

root[<child_identifier>]

를 선언하면 된다.

요약

  • collection.default를 사용해서 child node를 추가한다.
  • isEnd(True) 의 존재 유무로 string존재 유무 판별.
  • 편의성을 위해 isEnd가 있는 노드에는 value로서 string값을 넣어 놓는다.

다음은 예제로 "any", "anyway", "car" 를 넣은 trie를 만들어 보았다.

In [14]: 
1
2
3
4
5
6
7
8
9

_root = lambda: defaultdict(_root)  # 자기자신을 argument로 받는 dictionary. 
root = _root()
isEnd = True
for word in "car", "any", "anyway":
    cur = root
    for c in word:
        cur = cur[c]
    cur[isEnd] = word
pprint(root)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

defaultdict(<function <lambda> at 0x7f8ac4f9f830>,
            {'a': defaultdict(<function <lambda> at 0x7f8ac4f9f830>,
                              {'n': defaultdict(<function <lambda> at 0x7f8ac4f9f830>,
                                                {'y': defaultdict(<function <lambda> at 0x7f8ac4f9f830>,
                                                                  {True: 'any',
                                                                   'w': defaultdict(<function <lambda> at 0x7f8ac4f9f830>,
                                                                                    {'a': defaultdict(<function <lambda> at 0x7f8ac4f9f830>,
                                                                                                      {'y': defaultdict(<function <lambda> at 0x7f8ac4f9f830>,
                                                                                                                        {True: 'anyway'})})})})})}),
             'c': defaultdict(<function <lambda> at 0x7f8ac4f9f830>,
                              {'a': defaultdict(<function <lambda> at 0x7f8ac4f9f830>,
                                                {'r': defaultdict(<function <lambda> at 0x7f8ac4f9f830>,
                                                                  {True: 'car'})})})})

위의 Trick을 이용하여 문제를 푸는 아이디어는 다음과 같다.

  • 주어진 origins에 있는 word들로 Trie를 만들어 놓는다.
  • sentence를 word단위로 쪼개서 하나씩 replace함수를 통해 trie에서 조건에 맞는 단어를 origins에서 찾는다.
In [15]: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def replaceWords(self, origins, sentence):
        """ 각 word마다 가장 짧은 word in origins 로 교체한다. """

        # build trie
        _root = lambda: defaultdict(_root)
        root = _root()  # create root node in trie.
        isEnd = True  # mark isEnd to trick.
        for word in origins:
            cur = root
            for c in word:
                cur = cur[c]
            cur[isEnd] = word
        
        pprint(root)
        
        def replace(word):
            """ return the shortest word in origins by searching from root nodes to isEnd"""
            cur = root  # root node
            for c in word:
                if c not in cur:  # pruning
                    break
                cur = cur[c]  # dfs search.
                if isEnd in cur:  # if find word in origins,
                    return cur[isEnd]  # return stored word in origins.
            return word  # return literal word if any word not in origins.

        return " ".join(map(replace, sentence.split()))
In [16]: 
1
2
3
4

origins = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
sol = Solution()
print("answer: ", sol.replaceWords(origins, sentence))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

defaultdict(<function Solution.replaceWords.<locals>.<lambda> at 0x7f8ac475c050>,
            {'b': defaultdict(<function Solution.replaceWords.<locals>.<lambda> at 0x7f8ac475c050>,
                              {'a': defaultdict(<function Solution.replaceWords.<locals>.<lambda> at 0x7f8ac475c050>,
                                                {'t': defaultdict(<function Solution.replaceWords.<locals>.<lambda> at 0x7f8ac475c050>,
                                                                  {True: 'bat'})})}),
             'c': defaultdict(<function Solution.replaceWords.<locals>.<lambda> at 0x7f8ac475c050>,
                              {'a': defaultdict(<function Solution.replaceWords.<locals>.<lambda> at 0x7f8ac475c050>,
                                                {'t': defaultdict(<function Solution.replaceWords.<locals>.<lambda> at 0x7f8ac475c050>,
                                                                  {True: 'cat'})})}),
             'r': defaultdict(<function Solution.replaceWords.<locals>.<lambda> at 0x7f8ac475c050>,
                              {'a': defaultdict(<function Solution.replaceWords.<locals>.<lambda> at 0x7f8ac475c050>,
                                                {'t': defaultdict(<function Solution.replaceWords.<locals>.<lambda> at 0x7f8ac475c050>,
                                                                  {True: 'rat'})})})})
answer:  the cat was rat by the bat

Furthermore

defaultdict 로 trie자료구조의 function들을 구현해보자.

Step 1. Create root node

In [17]: 
1
2
3
4

# build trie
_root = lambda: defaultdict(_root)
root = _root()  # create root node in trie.
isEnd = True  # mark isEnd

Step 2. Insertion

In [18]: 
1
2
3
4
5
6
7
8
9

def insert(x):
    cur = root
    for c in x:
        cur = cur[c]
    cur[isEnd] = x

for word in keys:
    insert(word)
pprint(root)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

defaultdict(<function <lambda> at 0x7f8ac475c320>,
            {'a': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                              {True: 'a',
                               'n': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                {'s': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                  {'w': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                    {'e': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                                      {'r': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                                                        {True: 'answer'})})})}),
                                                 'y': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                  {True: 'any'})})}),
             'b': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                              {'y': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                {'e': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                  {True: 'bye'})})}),
             't': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                              {'h': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                {'e': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                  {True: 'the',
                                                                   'i': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                    {'r': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                                      {True: 'their'})}),
                                                                   'r': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                    {'e': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                                      {True: 'there'})})})})})})
In [19]: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

def search(x):
    cur = root
    for c in x:
        if c not in cur.keys():
            return False
        cur = cur[c]
    return cur != root and isEnd in cur

output = ["Not present in trie", "Present in trie"]
print("{:<7} ---- {}".format("any", output[search("any")]))
print("{:<7} ---- {}".format("the", output[search("the")]))
print("{:<7} ---- {}".format("these", output[search("these")]))
print("{:<7} ---- {}".format("their", output[search("their")]))
print("{:<7} ---- {}".format("thaw", output[search("thaw")]))

1
2
3
4
5
6

any     ---- Present in trie
the     ---- Present in trie
these   ---- Not present in trie
their   ---- Present in trie
thaw    ---- Not present in trie

Step4. Delete

In [20]: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def delete(x):
    def _delete(cur, j=0):
        if j == len(x):
            if isEnd in cur:
                cur.pop(isEnd)
            return bool(cur.keys())
        c = x[j]
        if c not in cur.keys():
            print("'{}' is not present".format(x))
            return True
        if _delete(cur[c], j + 1):
            return True
        cur.pop(c)
        return bool(cur.keys()) or isEnd in cur
    _delete(root)

insert("anyway")
delete("any")
print("{:<7} ---- {}".format("any", output[search("any")]))
pprint(root)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

any     ---- Not present in trie
defaultdict(<function <lambda> at 0x7f8ac475c320>,
            {'a': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                              {True: 'a',
                               'n': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                {'s': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                  {'w': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                    {'e': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                                      {'r': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                                                        {True: 'answer'})})})}),
                                                 'y': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                  {'w': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                    {'a': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                                      {'y': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                                                        {True: 'anyway'})})})})})}),
             'b': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                              {'y': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                {'e': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                  {True: 'bye'})})}),
             't': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                              {'h': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                {'e': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                  {True: 'the',
                                                                   'i': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                    {'r': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                                      {True: 'their'})}),
                                                                   'r': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                    {'e': defaultdict(<function <lambda> at 0x7f8ac475c320>,
                                                                                                      {True: 'there'})})})})})})

Reference

[1] https://www.geeksforgeeks.org/trie-insert-and-search/
[2] https://treelib.readthedocs.io/en/latest/treelib.html
[3] delete operation: stack overflow

Leave a comment

You may also enjoy

Reeds-Shepp (RS) Path

18 minute read

이동체의 운동 구속조건을 반영하면 전진과 후진 경로에 대한 48가지 경로의 조합을 체크하는 RS path를 배워보자.

Model Predictive Control (MPC)

17 minute read

motion model로 다음 상태를 예측하여 비용함수를 만들고 모델을 제약사항으로 최적화를 하여 제어값을 찾아내는 MPC에 대해서 배워보자

RRT star

15 minute read

RRT star 알고리즘에 대해서 알아보자.