208. Implement Trie (Prefix Tree) - python3

Implement a trie with insert, search, and startsWith methods.

My Answer 1: Accepted (Runtime: 652 ms - 5.02% / Memory Usage: 21.1 MB - 97.54%)

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = []

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        self.trie.append(word)

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        if word in self.trie:
            return True
        else:
            return False

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        for i in self.trie:
            if prefix in i and i.index(prefix) == 0:
                return True
        return False


# 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)

아 쉽다쉬워했건만,,
그렇게 비효율적으로 보이지도 않는거 같은데 런타임이 상당히 느리다..
리스트 때문인듯?!

Dictionary

Solution 1: Runtime: 116 ms - 99.07% / Memory Usage: 27.9 MB - 77.14%

class Trie:

    def __init__(self):
        self.root = {}
        self.ends_here = False

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node[self.ends_here] = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.ends_here in node

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        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)

딕셔너리를 이용한 방식

Solution 2: Runtime: 172 ms - 71.22% / Memory Usage: 31.7 MB - 41.68%

class TrieNode:
    def __init__(self):
        # Stores children nodes and whether node is the end of a word
        self.children = {}
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        cur = self.root
        # Insert character by character into trie
        for c in word:
            # if character path does not exist, create it
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.isEnd = True
        

    def search(self, word: str) -> bool:
        cur = self.root
        # Search character by character in trie
        for c in word:
            # if character path does not exist, return False
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.isEnd
        

    def startsWith(self, prefix: str) -> bool:
        # Same as search, except there is no isEnd condition at final return
        cur = self.root
        for c in prefix:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        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)

TrieNode 를 이용한 방식

Trie 공부하기~~!!