こんにちは
今回の学びは
・implement-trie-prefix-tree Trieは実装できるようになろう！
この問題はTrieの基本です。重要な問題と思います。
（時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装 20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）
３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）
timespace analysis (時間とスペースの分析）は 〇〇です
場合によっては、pseudocode（擬似コード）をかいてみてもよい。
https://leetcode.com/problems/implement-trie-prefix-tree/
apple
apo
a -> p -> p-> -> l -> e
-> o
calss Node:
value
next_nodes
is_end = False
Node(a), ... Node(z)
sO( 26 ^ n ) # doesn't scale, but , but realisticcly, there only about 2M words. so let's do this.
{
a: {p: {
p: { l: {e : {a: {}, end:1}}
o:
# Object, it can not track by index(key). Need to overwrite Dict
{
Na: {Pa: {
p: { l: {e : {}}
o:
# Let's write in using dict(dict...) and "end" entry as flag
# Let's write in using dict(dict...) and "end" entry as flag
"""
e: {
v: {
e: {
n: {
t: {
end: {}
}
}
end: {}
}
o: {
l: {v:{e:{end:{}}}}
}
}
}
"""
class Trie:
self.__init__():
self.db = {}
def insert(self, word: str) -> None:
curr = self.db
for i, c in enumerate(word):
if i == len(word) - 1: curr[c].update({"end":1})
else: curr[c].update({})
curr = curr[c]
def search(self, word: str) -> bool: # eve
curr = self.db
N = len(word)
i = 0
while i <= N and curr and word[i] in curr: # N=2, curr = {...}, e in
if i == len(word) -1 and "end" in curr[word[i]]:
return True
curr = curr[word[i]]
i+=1
return False
def startsWith(self, prefix: str) -> bool:
curr = self.db
N = len(prefix)
i = 0
while i <= N and curr and word[i] in curr: # e in curr_db?
if i == len(word) -1:
return True
curr = curr[word[i]]
i+=1
return False
４、実装しましょう。
class Trie:
def __init__(self):
self.db = {}
def insert(self, word: str) -> None:
curr = self.db
for i, c in enumerate(word):
if c in curr:
if i == len(word) - 1: curr[c].update({"end":{}})
else: curr[c].update({})
else:
if i == len(word) - 1: curr[c] = {"end":{}}
else: curr[c] = {}
curr = curr[c]
def search(self, word: str) -> bool: # eve
curr = self.db
N = len(word)
i = 0
while i < N and curr and word[i] in curr: # N=2, curr = {...}, e in
if i == len(word) -1 and "end" in curr[word[i]]:
return True
curr = curr[word[i]]
i+=1
return False
def startsWith(self, prefix: str) -> bool:
curr = self.db
N = len(prefix)
i = 0
while i <= N and curr and prefix[i] in curr: # e in curr_db?
if i == len(prefix) -1:
return True
curr = curr[prefix[i]]
i+=1
return False
# Your Trie object will be instantiated and called as such:
trie = Trie()
print(trie.insert("apple"))
print(trie.search("apple")) # returns true
print(trie.search("app")) # returns false
print(trie.startsWith("app")) # returns true
print(trie.insert("app"))
print(trie.search("app")) # returns true
５、エッジケースとサンプルテストを忘れずに！
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
Trieをdictで実装する
最初に考えた、Nodeを作ってやるやり方は私は検索がNodeだとできないと思ったが
[0] * 26でインデックスの箱を用意してやるやり方があったか。
setdefaultでかなりスッキリ書かれているパターン
https://leetcode.com/problems/implement-trie-prefix-tree/discuss/486556/Python-using-setdefault
スピードはそこそこ、私のより20%くらい速く
(py37new) 0122 11:46 aoj > Runtime: 200 ms, faster than 34.64% of Python3 online submissions for Implement Trie (Prefix Tree).
なぜか、私の2回目流すと一気に74%に改善、するとsetdefaultは遅いか！？
setdefaultとははじめてのPython！setdefaultで辞書のキーと値を追加する方法でみると、単純な便利関数っぽい動き、もっとよいバージョンがdefaultdictだと思うけど、実際あんまりパフォーマンスはよくなかった感じがしたよ。本家にもちょっと使われているケースが違うけど、defaultdictのがシンプルで速いとかいてあった。まぁでも、この実装はsetdefaultを使っているだけで、構成は私のと同じですね。
まとめ
・implement-trie-prefix-tree Trieは実装できるようになろう！
・この問題はimplement-trie-prefix-treeはTrieの基本です。重要な問題と思います。
以上です