いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 208 Implement Trie (Prefix Tree)

投稿日:

こんにちは

今回の学びは

implement-trie-prefix-tree Trieは実装できるようになろう!

 

 

問題はimplement-trie-prefix-tree

この問題はTrieの基本です。重要な問題と思います。

(時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装  20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。

終始、わからないことは声にだして、明確にしていきましょう。

1,まずは入出力をしっかりおさえましょう。(問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと)

 

2,いくつかのソリューションを声にだして出してみましょう。(もちろんtime complexit, space complexityの分析や理由を付け加えて)

 

3,どれでいくか、一緒に決定しましょう。(理由付きでね、よろしく)

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






 

 

4、実装しましょう。

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

5、エッジケースとサンプルテストを忘れずに!

 

 

 

振り返り

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

Trieをdictで実装する

 

最初に考えた、Nodeを作ってやるやり方は私は検索がNodeだとできないと思ったが

[0] * 26でインデックスの箱を用意してやるやり方があったか。

なるほどhttps://leetcode.com/problems/implement-trie-prefix-tree/discuss/487003/Python3-easy-to-understand-solution-using-a-list()

 

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-treeTrieの基本です。重要な問題と思います。

以上です

-アルゴリズム
-

Copyright© CTOの日記 , 2020 All Rights Reserved.