insert(), search(), startsWith() 메서드와 같은 세 가지 기본 작업을 사용하여 tri 구조를 만들어야 한다고 가정합니다. 모든 입력이 소문자라고 가정할 수 있습니다. 예를 들어 다음과 같이 함수를 호출하면 출력이 표시됩니다.
- 트라이 트라이 =새로운 트라이()
- trie.insert("사과")
- trie.search("apple") // true를 반환합니다.
- trie.search("app") //거짓을 반환합니다.
- trie.startsWith("app") // true를 반환합니다.
- trie.insert("앱")
- trie.search("app") // true를 반환합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 처음에는 child라는 사전을 하나 만듭니다.
- 삽입 방법은 다음과 같습니다 -
- 현재 :=자식
- 단어의 각 문자 l에 대해 −
- 현재에 l이 없으면 현재[l] :=새 사전
- 현재 :=현재[l]
- 현재[#] =1
- 검색 방법은 다음과 같습니다 -
- 현재 :=자식
- 단어의 각 문자 l에 대해 −
- 현재에 l이 없으면 false를 반환합니다.
- 현재 :=현재[l]
- 현재[#] =1이면 true를 반환하고, 그렇지 않으면 false를 반환
- startsWith 메소드는 다음과 같습니다 -
- 현재 :=자식
- 단어의 각 문자 l에 대해 −
- 현재에 l이 없으면 false를 반환합니다.
- 현재 :=현재[l]
- 참 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Trie(object):
def __init__(self):
self.child = {}
def insert(self, word):
current = self.child
for l in word:
if l not in current:
current[l] = {}
current = current[l]
current['#']=1
def search(self, word):
current = self.child
for l in word:
if l not in current:
return False
current = current[l]
return '#' in current
def startsWith(self, prefix):
current = self.child
for l in prefix:
if l not in current:
return False
current = current[l]
return True
ob1 = Trie()
ob1.insert("apple")
print(ob1.search("apple"))
print(ob1.search("app"))
print(ob1.startsWith("app"))
ob1.insert("app")
print(ob1.search("app")) 입력
ob1 = Trie()
ob1.insert("apple")
print(ob1.search("apple"))
print(ob1.search("app"))
print(ob1.startsWith("app"))
ob1.insert("app")
print(ob1.search("app")) 출력
True False True True