[leetcode] 3-13회차

https://leetcode.com/problems/implement-trie-prefix-tree/?envType=study-plan-v2&envId=top-interview-150

 

trie 문제다.

문제는 내가 trie 자료구조가 기억이 안난다.

기억을 살릴 겸 블로그를 살펴본다.

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie

[자료구조] 트라이 (Trie)

 

https://codingnojam.tistory.com/40

[Algorithm] Trie를 Java로 구현해보자!

이곳저곳 찾아보니 구현방법이 달랐는데 언어 차이인걸까?

 

java 나 c 언어의 경우에는 endofWord 나 finish 등의 bool 변수로 확인하는데 반해

python 은 리프노드에 word 를 저장하는 게 달랐다.

같은 이유로 구현한거니 상관 없을 것 같다.

 

class Trie(object):

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

    def insert(self, word):
        """
        :type word: str
        :rtype: None
        """
        cur=self.root

        for letter in word:
            if letter not in cur:
                cur[letter]={}
            cur=cur[letter]

        cur['*']=''
    

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        cur=self.root
        for letter in word:
            if letter not in cur:
                return False
            cur=cur[letter]

        return '*' in cur

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

 

 

https://leetcode.com/problems/design-add-and-search-words-data-structure/description/?envType=study-plan-v2&envId=top-interview-150

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_node = False

class WordDictionary(object):

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

    def addWord(self, word):
        """
        :type word: str
        :rtype: None
        """
        cur = self.root

        for letter in word:
            cur = cur.children.setdefault(letter, TrieNode())


        cur.end_node = True

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        def dfs(node, i):
            if i == len(word): return node.end_node

            if word[i] == ".":
                for child in node.children:
                    if dfs(node.children[child], i+1): return True
            
            if word[i] in node.children:
                return dfs(node.children[word[i]], i+1)

            return False
            
        return dfs(self.root, 0)

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

 

기능 하나 추가하는건데 어려웠다.

열심히 공부하자.