[PYTHON] Let Code Day 38 starting from scratch "208. Implement Trie (Prefix Tree)"

Overview

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.

Leetcode

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.

problem

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.

solution

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.