208.Implement Trie (Prefix Tree) === ###### tags: `Medium`,`Trie`,`String`,`Hash Table` [208. Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/) ### 題目描述 A [trie](https://en.wikipedia.org/wiki/Trie) (pronounced as "try") or **prefix tree** is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: * `Trie()` Initializes the trie object. * `void insert(String word)` Inserts the string `word` into the trie. * `boolean search(String word)` Returns `true` if the string `word` is in the trie (i.e., was inserted before), and `false` otherwise. * `boolean startsWith(String prefix)` Returns `true` if there is a previously inserted string `word` that has the prefix `prefix`, and `false` otherwise. ### 範例 **Example 1:** ``` Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, null, true, false, true, null, true] Explanation Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True ``` **Constraints**: * 1 <= `word.length`, `prefix.length` <= 2000 * `word` and `prefix` consist only of lowercase English letters. * At most 3 * 10^4^ calls **in total** will be made to `insert`, `search`, and `startsWith`. ### 解答 #### Python ```python= class Trie: def __init__(self): self.trie = {} def insert(self, word: str) -> None: node = self.trie for c in word: node = node.setdefault(c, {}) node['$'] = True def search(self, word: str) -> bool: node = self.trie for c in word: if not (node := node.get(c)): return False return '$' in node def startsWith(self, prefix: str) -> bool: node = self.trie for c in prefix: if not (node := node.get(c)): return False return True ``` > [name=Ron Chen][time=Fri, Mar 17, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)