It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.
As a countermeasure, it seems that a site called Let Code will take measures.
A site that trains algorithmic power that can withstand coding tests that are often done in the home.
I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.
Leet Code Table of Contents Starting from Zero
Last time Leet Code Day 37 "105. Construct Binary Tree from Preorder and Inorder Traversal"
I'm currently solving the Top 100 Liked Questions Medium. I solved all Easy, so if you are interested, please go to the table of contents.
Twitter I'm doing it.
208. Implement Trie (Prefix Tree) The difficulty level is Medium. Excerpt from Top 100 Liked Questions.
The problem is that you should implement the insert, search, and startswith functions in a class called Trie.
In addition, as each behavior,
Trie trie = new Trie();
trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app");
trie.search("app"); // returns true
It looks like this.
Basically, all the arguments are checked once with the for statement, and if it does not exist in the originally held ʻelement,
Falseis returned or
{}` is substituted.
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.element = {}
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
inserted = self.element
for tmp in word:
if tmp not in inserted:
inserted[tmp] = {}
inserted = inserted[tmp]
inserted["-"] = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
searched = self.element
for tmp in word:
if tmp not in searched:
return False
searched = searched[tmp]
return "-" in searched
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
started = self.element
for tmp in prefix:
if tmp not in started:
return False
started = started[tmp]
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)
# Runtime: 128 ms, faster than 94.63% of Python3 online submissions for Implement Trie (Prefix Tree).
# Memory Usage: 27.3 MB, less than 66.67% of Python3 online submissions for Implement Trie (Prefix Tree).
I was able to implement it faster than I expected.
As far as the discussion is concerned, the other major answer was
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
# Runtime: 192 ms, faster than 57.66% of Python3 online submissions for Implement Trie (Prefix Tree).
# Memory Usage: 32.5 MB, less than 7.41% of Python3 online submissions for Implement Trie (Prefix Tree).
It was like this.
You created a separate class called TrieNode
and used something called defaultdict.
However, regarding this time, I think the former answer is easier to understand and faster, so I think that is better.
This time it looks like this, thank you for your hard work.
Recommended Posts