1. What I learned
Trie
Trie is a tree structure called prefix tree that stores a string in a tree format so that it does not overlap if it contains the same alphabet. It is efficient because it takes O(n) to retrieve strings.
class Node:
def __init__(self, key):
self.key = key
self.children = {}
self.isEnd = False
class Trie:
def __init__(self):
self.head = Node(None)
def insertWord(self, word):
cur = self.head
for e in word:
if e not in cur.children:
cur.children[e] = Node(e)
cur = cur.children[e]
cur.isEnd = True
trie = Trie()
trie.insert("hello")
trie.insert("helloworld")
# None --> "h" --> "e" --> "l" --> "l" --> "o" --> "w" --> "o" --> "r" --> "l" --> "d"
2. Code
class Solution:
def longestWord(self, words: List[str]) -> str:
word_set = set()
result = ""
words.sort() # to obtain result in the smallest lexical order
for word in words:
if len(word)==1 or word[:-1] in word_set: # This is a trie concept, which means that word[:-1] is in word_set.
if len(result) < len(word):
result = word
word_set.add(word)
return result
3. Result
Runtime : 64 ms(98.64%), Memory usage : 14.5 MB(79.08%)
(Runtime can be different by a system even if it is a same code.)