208

YujueY · YujueY · commit 29eb1ed1a771 · 2020-07-26T13:14:00.000+08:00
diff --git a/Week07/208.py b/Week07/208.py
@@ -0,0 +1,39 @@
+class Trie:
+
+    def __init__(self):
+        """
+        Initialize your data structure here.
+        """
+        self.root = {}
+        self.end_of_word = "#"
+
+    def insert(self, word: str) -> None:
+        """
+        Inserts a word into the trie.
+        """
+        node = self.root
+        for char in word:
+            node = node.setdefault(char, {})
+        node[self.end_of_word] = self.end_of_word
+
+    def search(self, word: str) -> bool:
+        """
+        Returns if the word is in the trie.
+        """
+        node = self.root
+        for char in word:
+            if char not in node:
+                return False
+            node = node[char]
+        return self.end_of_word in node
+
+    def startsWith(self, prefix: str) -> bool:
+        """
+        Returns if there is any word in the trie that starts with the given prefix.
+        """
+        node = self.root
+        for char in prefix:
+            if char not in node:
+                return False
+            node = node[char]
+        return True
