【LeetCode】208.實作Trie（字首樹）

• 感覺這個python版的代碼比C版的代碼好寫多了

1.題目

2.分析

• isEnd：表示目前這個節點是否是葉子節點
• next：表示目前這個葉子節點的後序連結清單節點

3.代碼

class Trie:
    def __init__(self):
        self.isEnd = False # 判斷目前字元是否結尾字元
        self.next = [None] * 26 # 用于接注後序的字元，存儲的仍然是一個Trie節點
    
    # 插入節點的時候，需要疊代更新這個節點參數
    def insert(self, word: str) -> None:
        root = self # 表示目前值
        for i in range(len(word)):
            cur = word[i] # 目前字元
            idx = ord(cur) - ord('a') # 得到下标
            if root.next[idx] is None: # 如果為None
                new_node = Trie()
                root.next[idx] = new_node # 
                root = new_node # 更新節點值
            else:
                root = root.next[idx]            
        root.isEnd = True            

    def search(self, word: str) -> bool:
        root = self
        for i in range(len(word)):
            cur = word[i]
            idx = ord(cur) - ord('a')
            if root.next[idx]:
                root = root.next[idx]
            else:
                return False

        return root.isEnd
            

    def startsWith(self, prefix: str) -> bool:
        root = self
        for i in range(len(prefix)):
            cur = prefix[i]
            idx = ord(cur) - ord('a')
            if root.next[idx]:
                root = root.next[idx]
            else:
                return False
        return True
            

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)