자동완성 구현
트라이
문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
트리구조로 간선은 이전 정점으로 새롭게 추가되는 문자 정보를 가지고 있다.
정점은 이전 정점으로부터 더해진 문자열 정보를 가지고 있다.
이런식으로 미리 정의한 문자열로 자동완성을 구현할 수 있다.
- 문자열을 탐색할 때 효율적
- L이 문자열이의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
- 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다.
구현
- 루트 노드는 비어있다.
- cat라는 문자열을 추가할 때
- c를 키로 가지는 자식을 루트 노드에 추가한다.
- a를 키로 가지는 자식을 c를 키로 가지는 노드에 추가한다.
- t를 키로 가지는 자식을 a를 키로 가지는 노드에 추가한다.
def Node:
def __init__(self, value = ""):
self.value = value
self.children = dict()
def Trie(self):
def __init__(self, string):
self.root = Node()
def insert(self, string):
cur = self.root
for char in string:
if char not in cur.children:
cur.children[char] = Node(cur.value + char)
cur = cur.children[char]
def has(self, string):
cur = self.root
for char in string:
if char not in cur.children:
return False
cur = cur.children[char]
return True
Author And Source
이 문제에 관하여(자동완성 구현), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@alslahdk/자동완성-구현저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)