Trie(접두사 트리) 구현

4170 단어 theabbieleetcodedsa
Atrie("try"로 발음) 또는 접두사 트리는 문자열 데이터 세트에서 키를 효율적으로 저장하고 검색하는 데 사용되는 트리 데이터 구조입니다. 자동 완성 및 맞춤법 검사기와 같은 이 데이터 구조의 다양한 응용 프로그램이 있습니다.

Trie 클래스를 구현합니다.
  • Trie() trie 개체를 초기화합니다.
  • void insert(String word) 트라이에 문자열word을 삽입합니다.
  • boolean search(String word) 문자열true이 트리에 있으면(즉, 이전에 삽입된 경우) word를 반환하고 그렇지 않으면 false를 반환합니다.
  • boolean startsWith(String prefix) 접두사가 true 인 이전에 삽입된 문자열word이 있는 경우 prefix를 반환하고 그렇지 않은 경우 false를 반환합니다.

  • 예 1:

    입력
    ["Trie", "삽입", "검색", "검색", "startsWith", "삽입", "검색"]
    [[], ["사과"], ["사과"], ["앱"], ["앱"], ["앱"], ["앱"]]
    산출
    [널, 널, 참, 거짓, 참, 널, 참]

    설명
    트라이 트라이 = new 트라이();
    trie.insert("사과");
    trie.search("사과");//참 반환
    trie.search("앱");//거짓 반환
    trie.startsWith("앱");//참 반환
    trie.insert("앱");
    trie.search("앱");//참 반환

    제약:
  • 1 <= word.length, prefix.length <= 2000
  • wordprefix는 영문 소문자로만 구성됩니다.
  • 최대 3 * 104 호출은 insert , searchstartsWith 로 이루어집니다.

  • 해결책:

    class Node:
        def __init__(self, val=None, children=[], end=False):
            self.val = val
            self.children = children
            self.end = end
    
    class Trie:
        def __init__(self):
            self.root = Node(val=None, children=[])
    
        def insert(self, word: str) -> None:
            n = len(word)
            curr = self.root
            for i, c in enumerate(word):
                found = False
                for node in curr.children:
                    if node.val == c:
                        curr = node
                        found = True
                        break
                if not found:
                    newcurr = Node(val=c, children=[])
                    curr.children.append(newcurr)
                    curr = newcurr
            curr.end = True
    
        def search(self, word: str) -> bool:
            n = len(word)
            curr = self.root
            for i, c in enumerate(word):
                found = False
                for node in curr.children:
                    if node.val == c:
                        curr = node
                        found = True
                        break
                if not found:
                    return False
            return curr.end
    
        def startsWith(self, prefix: str) -> bool:
            n = len(prefix)
            curr = self.root
            for i, c in enumerate(prefix):
                found = False
                for node in curr.children:
                    if node.val == c:
                        curr = node
                        found = True
                        break
                if not found:
                    return False
            return True
    
    # class Trie:
    
    #     def __init__(self):
    #         self.trie = {}
    
    #     def insert(self, word: str) -> None:
    #         word = list(word) + [-1]
    #         n = len(word)
    #         for i in range(n - 1):
    #             if i not in self.trie:
    #                 self.trie[i] = {}
    #             if word[i] in self.trie[i]:
    #                 self.trie[i][word[i]].add(word[i + 1])
    #             else:
    #                 self.trie[i][word[i]] = {word[i + 1]}
    
    #     def search(self, word: str, isPartial = False) -> bool:
    #         if not isPartial:
    #             word = list(word) + [-1]
    #         n = len(word)
    #         if n == 1:
    #             if word[0] in self.trie.get(0, {}):
    #                 return True
    #             else:
    #                 return False
    #         for i in range(n - 1):
    #             if i not in self.trie or word[i] not in self.trie[i] or word[i + 1] not in self.trie[i][word[i]]:
    #                 return False
    #         return True
    
    #     def startsWith(self, prefix: str) -> bool:
    #         return self.search(prefix, isPartial = 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)
    

    좋은 웹페이지 즐겨찾기