Trie가 있고 사용자가 문자를 입력할 때 일치하는 문자열을 Trie로 표시해야 합니다. 이 기능을 자동 완성이라고 합니다. 예를 들어 시도에 "xyzzzz,""xyz," "xxxyyxzzz"가 포함된 경우 사용자가 xy를 입력하면 , 그러면 우리는 그들에게 xyzzzz, xyz를 보여주어야 합니다. 등.
결과를 얻기 위한 단계.
-
표준 Trie 알고리즘을 사용하여 문자열을 검색합니다.
-
문자열이 없으면 -1을 반환합니다.
-
문자열이 존재하고 Trie에서 단어의 끝이면 문자열을 인쇄합니다.
-
일치하는 문자열에 노드가 없으면 반환합니다.
-
그렇지 않으면 모든 노드를 인쇄합니다.
코딩을 시작하겠습니다.
# class for Trie Node
class TrieNode():
def __init__(self):
# initialising trie node
self.trie_node = {}
self.last_node = False
class Trie():
def __init__(self):
# initialising the trie
self.root = TrieNode()
# list to store the words
self.words = []
def create_trie(self, keys):
# creating the Trie using data
for key in keys:
# inserting one key to the trie
self.insert_node(key)
def insert_node(self, key):
node = self.root
for obj in list(key):
if not node.trie_node.get(obj):
# creating a TrieNode
node.trie_node[obj] = TrieNode()
node = node.trie_node[obj]
# making leaf node
node.last_node = True
def search(self, key):
# searching for the key
node = self.root
is_found = True
for obj in list(key):
if not node.trie_node.get(obj):
is_found = False
break
node = node.trie_node[obj]
return node and node.last_node and is_found
def matches(self, node, word):
if node.last_node:
self.words.append(word)
for obj, n in node.trie_node.items():
self.matches(n, word + obj)
def show_auto_completion(self, key):
node = self.root
is_found = False
temp = ''
for obj in list(key):
# checking the word
if not node.trie_node.get(obj):
is_found = True
break
temp += obj
node = node.trie_node[obj]
if is_found:
return 0
elif node.last_node and not node.trie_node:
return -1
self.matches(node, temp)
for string in self.words:
print(string)
return 1
# data for the Trie
strings = ["xyz", "xyzzzz", "xyabad", "xyyy", "abc", "abbccc", "xyx", "xyxer",
a"]
# word for auto completion
string = "xy"
status = ["Not found", "Found"]
# instantiating Trie class
trie = Trie()
# creating Trie using the strings
trie.create_trie(strings)
# getting the auto completion words for the string from strings
result = trie.show_auto_completion(string)
if result == -1 or result == 0:
print("No matches") 위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
xyz xyzzzz xyabad xyyy xyx xyxer