ゼロから始めるLeetCode Day38「208. Implement Trie (Prefix Tree)」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day37「105. Construct Binary Tree from Preorder and Inorder Traversal」
次回
ゼロから始めるLeetCode Day39「494. Target Sum」

今は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というものを使っていますね。
ただ、今回に関していえば前者の回答の方が分かりやすく、そして速いと思うのでそちらの方が良いのかなとは思います。

今回はこんな感じです、お疲れ様でした。