homework

confidence93 · confidence93 · commit 144eaa435897 · 2019-06-30T23:40:14.000+08:00
diff --git a/Week_04/id_14/Leetcode_208_14.py.txt b/Week_04/id_14/Leetcode_208_14.py.txt
@@ -0,0 +1,53 @@
+from collections import defaultdict
+
+
+class TrieNode(object):
+    def __init__(self):
+        """
+        Initialize your data structure here.
+        """
+        self.nodes = defaultdict(TrieNode)  # Easy to insert new node.
+        self.isword = False  # True for the end of the trie.
+
+
+class Trie(object):
+    def __init__(self):
+        self.root = TrieNode()
+
+    def insert(self, word):
+        """
+        Inserts a word into the trie.
+        :type word: str
+        :rtype: void
+        """
+        curr = self.root
+        for char in word:
+            curr = curr.nodes[char]
+        curr.isword = True
+
+    def search(self, word):
+        """
+        Returns if the word is in the trie.
+        :type word: str
+        :rtype: bool
+        """
+        curr = self.root
+        for char in word:
+            if char not in curr.nodes:
+                return False
+            curr = curr.nodes[char]
+        return curr.isword
+
+    def startsWith(self, prefix):
+        """
+        Returns if there is any word in the trie
+        that starts with the given prefix.
+        :type prefix: str
+        :rtype: bool
+        """
+        curr = self.root
+        for char in prefix:
+            if char not in curr.nodes:
+                return False
+            curr = curr.nodes[char]
+        return True
diff --git a/Week_04/id_14/Leetcode_720_14.py.py b/Week_04/id_14/Leetcode_720_14.py.py
@@ -0,0 +1,57 @@
+class TrieNode:
+    def __init__(self):
+        self.children = {}
+        self.end = False
+        
+class Trie:
+    def __init__(self):
+        self.root = TrieNode()
+    
+    def insert(self, word):
+        cur = self.root
+        for c in word:
+            if c not in cur.children:
+                cur.children[c] = TrieNode()
+            cur = cur.children[c]
+        cur.end = True
+    
+    def longest_word(self):
+        def helper(node, partial_res):
+            res = partial_res
+            for c, child in node.children.items():
+                if child.end:
+                    pot = helper(child, partial_res + c)
+                    if len(pot) > len(res):
+                        res = pot
+                    elif len(pot) == len(res) and pot < res:
+                        res = pot
+            return res
+        return helper(self.root, '')
+
+class Solution:
+    def longestWord(self, words):
+        """
+        :type words: List[str]
+        :rtype: str
+        """
+        T = Trie()
+        for word in words:
+            T.insert(word)
+        return T.longest_word()
+
+
+�ⷨ��:
+class Solution(object):
+    def longestWord(self, words):
+        """
+        :type words: List[str]
+        :rtype: str
+        """
+        words.sort()
+        words_set, longest_word = set(['']), ''
+        for word in words:
+            if word[:-1] in words_set:
+                words_set.add(word)
+                if len(word) > len(longest_word):
+                    longest_word = word
+        return longest_word
