[Python] 문자열 알고리즘 - Trie

Trie는 문자열 검색 알고리즘 중 하나로, 문자열을 저장하고 검색하는 데 유용합니다.

이진 탐색 트리와 달리, Trie는 문자열을 저장하는 트리 자료구조입니다.

Trie의 각 노드가 문자열의 한 문자에 대응되는 것입니다.

Trie를 이용해 문자열을 빠르게 검색 할 수 있습니다.

검색을 수행할 문자열을 루트에서 시작해 각 문자에 해당하는 노드들을 따라 검색을 합니다.

class Node:
    def __init__(self,text):
        self.text = text
        self.last = 0
        self.child = {}
        
class Trie:
    
    def __init__(self):
        self.no = 0
        self.root = Node(None)
    
    def add(self,text):
        currentNode = self.root
        for t in text:
            if t not in currentNode.child:
                self.no +=1
                currentNode.child[t] = Node(t)
                print(f"ADD : {t} || Current No. : {self.no}")
            currentNode = currentNode.child[t]
        currentNode.last = 1
        print(f"TOTAL : {self.no}")
        
    def find(self,text):
        result = ""
        currentNode = self.root
        for t in text:
            if t in currentNode.child:
                result += t
                currentNode = currentNode.child[t]
        return result