#概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day37「105. Construct Binary Tree from Preorder and Inorder Traversal」
今はTop 100 Liked QuestionsのMediumを解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。
Twitterやってます。
問題
208. Implement Trie (Prefix Tree)
難易度はMedium。
Top 100 Liked Questionsからの抜粋です。
問題としては、insert関数、search関数、startsWith関数をTrieというクラスにまとめて実装してください、というものです。
なお、それぞれの挙動としては、
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
このようになります。
解法
基本的に全ての引数を一度for文でチェックし、元々保持しているelementの中に存在しない場合はFalseを返すか、{}を代入するというものです。
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).
思ったよりスピードがでて良い感じに実装できました。
なお、discussをみる限り、他にメジャーな解答だったのは、
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).
こういったものでした。
TrieNodeというクラスを別に作り、defaultdictというものを使っていますね。
ただ、今回に関していえば前者の回答の方が分かりやすく、そして速いと思うのでそちらの方が良いのかなとは思います。
今回はこんな感じです、お疲れ様でした。