題目

  • 題目連結
  • 目標函式 :
    • Trie()
    • void insert(String word)
    • boolean search(String word)
    • boolean startsWith(String prefix)

解題概念

  • 題意 : 需要實作 Trie class
    • Trie() : 對 Trie 進行初始化
    • void insert(String word) : 插入字串 word 到 Trie 中
    • boolean search(String word) : 判斷字串 word 是否儲存在 Trie 中
    • boolean startsWith(String prefix) : 判斷 Trie 中的字串是否有 prefix

我的寫法

  • 想法 : 直接使用一個陣列去儲存字串就好
    • 在 startsWith() 中，針對 Trie 中每個字串 w 去判斷 prefix == w[:len(prefix)]
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Trie(object):

    def __init__(self):
        self.t_list = []

    def insert(self, word):
        self.t_list.append(word)
        

    def search(self, word):
        return word in self.t_list

    def startsWith(self, prefix):
        for w in self.t_list:
            if prefix == w[:len(prefix)]:
                return True
        return False
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 810 ms (faster than 5.1%)
    • Memory Usage: 21.2 MB (more than 96.74%)

解答 or 其他優秀寫法

  • 想法 : 使用 Tree 去表示 Trie Tree，其中原本使用 Node 去儲存，但這裡改使用 dict 以減省空間

    • dict 儲存格式 : {"a" : {"p" : {"p" : {"$" : ""}}}}
      • 其中使用 {"$" : ""} 當作 Leaf 的表示方法
    • 詳細說明請見程式碼

  • 程式碼 : 

    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
    class Trie(object):

        def __init__(self):
        self.root = {}

        def insert(self, word):
            # 從 root 開始搜尋
            ptr = self.root
            for char in word:
                # 若發現 char 與目前 ptr 不同，則要新創分支
                if char not in ptr:
                    ptr[char] = {}
                
                # ptr 向下一格
                ptr = ptr[char]

            # 將 Leaf 設定好
            ptr["$"] = ""
            

        def search(self, word):
            # 從 root 開始搜尋
            ptr = self.root
            for char in word:
                # 若發現 char 與目前 ptr 不同
                if char not in ptr:
                    return False # 則代表 word 不存在 Trie Tree 中

                # ptr 向下一格
                ptr = ptr[char]
            
            return "$" in ptr # 判斷當前 ptr 是否已到達 Leaf

        def startsWith(self, prefix):
            # 從 root 開始搜尋
            ptr = self.root
            for char in prefix:
                # 若發現 char 在 ptr 中無此分支
                if char not in ptr:
                    return False # 代表無此 prefix
                # ptr 向下一格
                ptr = ptr[char]
            return True

  • 成效 :

    • Time Complexity : $O(\log n)$
    • Runtime: 93 ms (faster than 96.87%)
    • Memory Usage: 29.9 MB (more than 29.9%)