Implement Trie (Prefix Tree)
트라이 또는 접두사 트리는 단어의 시작 부분에 관한 질문에 빠르게 답할 수 있도록 단어를 저장합니다. 소문자 단어를 위한 트라이를 만들고 세 가지 연산을 지원하세요. insert w는 단어 w를 추가하고, search w는 w 자체가 추가되었는지 알려 주며, startsWith p는 추가된 단어 중 p로 시작하는 단어가 있는지 알려 줍니다. 단어는 자기 자신의 접두사로 간주됩니다.
연산은 순서대로 ops로 주어지고, words[i]는 ops[i]에 해당하는 단어 또는 접두사입니다. 처음에 비어 있는 하나의 트라이에서 연산을 실행하고, 연산마다 문자열 하나를 반환하세요. 삽입의 경우 "null"을, 검색이나 startsWith의 경우 "true" 또는 "false"를 반환합니다.
함수
- opsstring-array
- 연산이 실행되는 순서대로
- wordsstring-array
- 각 연산을 나타내는 단어 또는 접두사
- 반환값string-array
- 연산마다 하나의 답변을 텍스트로
제약 조건
1 ≤ ops.length ≤ 2000words.length == ops.length- 각
ops[i]는insert,search또는startsWith입니다. 1 ≤ words[i].length ≤ 20words[i]에는 소문자 영어 알파벳만 들어 있습니다.
예제
- 입력
- ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
- 출력
- ["null", "false", "true", "null", "true"]
- 설명
- 처음에는
card만 저장되어 있으므로car를 검색하면"false"가 반환됩니다.car는 단어로 삽입된 적이 없습니다.card의 시작 부분이므로startsWith car는"true"를 반환합니다.car를 삽입하면 검색에서 찾을 수 있습니다.
- 입력
- ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
- 출력
- ["null", "null", "true", "false", "false", "true", "true"]
- 설명
- 두 단어 모두
te로 시작하므로startsWith te는"true"이지만, 정확히te인 단어는 없으므로 검색에 실패합니다.tex로 시작하는 단어는 없습니다.ten이 삽입되었고,tea는 자기 자신의 접두사이므로 마지막 두 답은"true"입니다.
- 입력
- ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
- 출력
- ["false", "false", "null", "true", "false", "true"]
- 설명
- 트라이는 비어 있는 상태로 시작하므로 처음 두 답은
"false"입니다.dog가 삽입된 후 검색에서 이를 찾고,dogs로 시작하는 단어는 없으며,do는dog의 시작 부분입니다.
제출 시 숨은 테스트 +16개
후속 질문
여전히 O(L) 시간 내에, p로 시작하는 서로 다른 저장된 단어의 개수를 반환하는 countPrefix p 연산을 어떻게 추가할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
전체 단어의 집합은 한 번의 조회로
search에 답을 제공하지만, 각 단어를 하나씩 확인하지 않고는 어떤 단어가te로 시작하는지 알 수 없습니다. 같은 방식으로 시작하는 단어들이 그 시작 부분의 저장 공간을 공유한다면 어떨까요?각 노드가 접두사를 나타내고, 다음에 올 수 있는 각 문자마다 하나의 자식 링크를 갖는 트리를 만드세요. 그러면 단어는 루트에서 시작하는 경로가 됩니다. 저장된 단어가 정확히 그 지점에서 끝나는지 나타내는 플래그를 각 노드에 두세요.
모든 연산은 루트에서 시작해 글자를 따라갑니다.
insert는 없는 노드를 만들고 마지막 노드에 플래그를 설정합니다.startsWith는 탐색이 끝까지 도달하면 성공합니다.search는 멈춘 노드에 플래그가 설정되어 있어야 합니다.
풀이
해시 집합은 search에 즉시 답하지만, startsWith는 특정 방식으로 시작하는 모든 단어에 대해 묻고, 집합에는 시작 부분이라는 개념이 없습니다. 트라이는 시작 부분 자체를 저장합니다. 모든 단어는 루트에서 출발하는 글자들의 경로이며, 같은 방식으로 시작하는 단어들은 경로의 시작 부분을 공유하고, 노드에 있는 플래그는 저장된 단어가 끝나는 지점을 표시합니다. 그러면 두 질문 모두 저장된 단어의 수와 관계없이, 질의의 길이인 L이 얼마든 최대 L개의 링크를 따라 한 번 이동하면 답할 수 있습니다.
단어 목록을 유지하고 이를 훑어보세요
핵심 아이디어
삽입한 모든 단어를 목록에 보관하세요. search w의 경우 w를 저장된 각 단어와 비교합니다. startsWith p의 경우 저장된 단어 중 p로 시작하는 단어가 있는지 확인합니다. 두 번째 예시에서 startsWith te는 먼저 tea를 확인하고 거기서 멈춥니다. startsWith tex는 "false"라고 답하기 전에 두 단어를 모두 확인해야 합니다.
이 방법은 올바르고 여기서 주어진 제한 안에서는 완료되지만, 모든 쿼리에 저장된 모든 단어를 확인하는 비용이 듭니다. n개의 단어가 저장되어 있으면 쿼리 하나에 최대 n번의 비교가 필요하며, 비교마다 최대 L개의 문자를 확인합니다. 저장된 단어가 1,000개이고 쿼리가 1,000개라면 문자열 비교가 백만 번 발생하며, 사전이 커질수록 작업량도 계속 늘어납니다. 또한 아무것도 공유되지 않습니다. tea와 ten은 각각 자기만의 t와 e를 저장합니다.
알고리즘
- 빈 단어 목록으로 시작합니다.
insert w의 경우: 목록에w를 추가합니다.search w의 경우: 저장된 단어 중 하나가w와 같은지 반환합니다.startsWith p의 경우: 저장된 단어 중 하나가p로 시작하는지 반환합니다.- 각 답을 텍스트로 기록하고 목록을 반환합니다.
def trieOps(ops, words):
stored = []
result = []
for op, word in zip(ops, words):
if op == "insert":
stored.append(word)
result.append("null")
elif op == "search":
found = any(s == word for s in stored)
result.append("true" if found else "false")
else:
found = any(s.startswith(word) for s in stored)
result.append("true" if found else "false")
return result트라이: 자식 링크와 종료 플래그
핵심 아이디어
트라이의 각 노드는 하나의 접두사를 나타냅니다. 접두사는 루트에서 해당 노드까지 내려가는 경로상의 문자들입니다. 루트는 빈 접두사를 나타냅니다. 노드에는 두 가지가 있습니다. 다음에 올 수 있는 각 문자에 대한 자식 링크(26개의 슬롯이 있는 배열 또는 문자에서 노드로의 맵)와 저장된 단어가 정확히 이 노드에서 끝나는지를 나타내는 플래그 isEnd입니다.
insert는 루트에서 시작해 단어를 따라갑니다. 각 문자에 대해 자식 링크를 따라가며, 링크가 없으면 먼저 노드를 만듭니다. 마지막 문자에서는 isEnd를 설정합니다. 두 번째 예시에서 tea를 삽입하면 t, te, tea에 해당하는 노드가 생성되고 tea가 표시됩니다. ten을 삽입하면 t와 te를 재사용하고 ten만 추가합니다. 두 단어는 te까지의 경로를 공유하며, 여기서 접두사 트리라는 이름이 유래합니다.
search와 startsWith는 아무것도 생성하지 않고 같은 경로를 따라갑니다. 링크가 없으면 저장된 단어 중 그 문자들로 시작하는 단어가 없으므로 둘 다 false를 반환합니다. tex는 te 노드에서 멈추는데, 그 노드에는 x 링크가 없습니다. 경로의 끝에 도달하면 현재 위치한 노드가 확인하려는 접두사입니다. startsWith는 true를 반환하고, search는 해당 노드의 플래그 값을 반환합니다. te 노드는 존재하지만, 이 노드를 거치는 단어들이 더 아래에서 끝나기 때문에 플래그는 꺼져 있습니다. 따라서 startsWith te는 true이고 search te는 false입니다.
플래그가 단어와 접두사를 구분합니다. 첫 번째 예시에서 card를 삽입하면 c, a, r 경로가 존재합니다. 플래그가 없다면 search car는 잘못해서 true를 반환할 것입니다. 나중에 car를 삽입해도 노드는 전혀 새로 만들어지지 않고 플래그만 켜집니다.
각 연산은 최대 L개의 링크를 따라가며, 여기서 L은 단어의 길이이므로 저장된 단어의 수와 관계없이 비용은 O(L)입니다. 트라이는 서로 다른 접두사마다 노드 하나를 가지며, 삽입된 문자의 총수보다 많은 노드를 가지는 일은 없습니다.
알고리즘
- 자식 링크(26개 슬롯 또는 맵)와
isEnd플래그를 가진 노드를 정의하고, 빈 루트를 만듭니다. insert w의 경우: 루트에서 시작해w의 각 문자에 해당하는 링크를 따라가며, 링크가 없으면 노드를 만듭니다. 마지막 노드에서isEnd를 설정합니다.- 도우미
find(p)를 작성합니다. 루트에서 시작해p의 각 문자에 해당하는 링크를 따라가고, 하나라도 없으면 즉시 중단합니다. 도달한 노드를 반환합니다. search w의 경우:find(w)가isEnd가 설정된 노드에 도달하면 true라고 답합니다.startsWith p의 경우:find(p)가 노드에 도달하면 true라고 답합니다.- 연산을 순서대로 실행하고 각각에 대해
"null","true"또는"false"를 기록합니다.
class TrieNode:
def __init__(self):
self.children = {} # letter -> TrieNode
self.is_end = False # does a stored word end at this node?
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def _find(self, prefix):
# Follow the letters from the root; None as soon as a link is missing.
node = self.root
for ch in prefix:
node = node.children.get(ch)
if node is None:
return None
return node
def search(self, word):
node = self._find(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._find(prefix) is not None
def trieOps(ops, words):
trie = Trie()
result = []
for op, word in zip(ops, words):
if op == "insert":
trie.insert(word)
result.append("null")
elif op == "search":
result.append("true" if trie.search(word) else "false")
else:
result.append("true" if trie.starts_with(word) else "false")
return result
함정과 경계 사례
대부분의 버그는 "단어가 여기서 끝난다"와 "단어가 여기를 지나간다"를 혼동해서 발생합니다.
- 경로가 존재할 때마다
search가 true를 반환하게 하는 경우입니다.card를 삽입한 뒤에는car의 경로가 존재하지만,car는 삽입된 적이 없습니다. - 새로 생성된 노드에만
isEnd를 설정하는 경우입니다.cards를 삽입한 뒤card를 삽입하면 아무것도 생성되지 않지만, 마지막 노드에는 여전히 해당 플래그가 필요합니다. - 링크가 이미 존재하는데도 새 자식 노드를 만드는 경우입니다. 그러면 그 아래에 저장된 모든 것이 끊깁니다. 예를 들어 새로운
t노드로ten을 삽입하면tea를 잃게 됩니다. - 단어는 자기 자신의 접두사이기도 하다는 점을 잊는 경우입니다.
tea를 삽입한 뒤에는startsWith tea가 true입니다. - 경로의 끝을 지나서 읽는 경우입니다. 저장된 단어가
sun뿐일 때sunny처럼 모든 단어보다 긴 접두사는 가장 먼저 누락된 링크에서 멈추고 false를 반환해야 합니다. - 불리언을 반환하거나 삽입 작업을 응답에서 누락하는 경우입니다. 삽입 작업의
"null"을 포함해 모든 작업은 문자열 하나를 반환합니다.
자주 묻는 질문4
트라이의 시간 복잡도는 얼마인가요?
Insert, search 및 startsWith는 각각 인수의 글자마다 링크 하나를 따라가므로, 길이가 L인 단어에 대해 저장된 단어 수와 관계없이 각각 O(L) 시간이 걸립니다. 트라이는 삽입된 글자마다 노드를 최대 하나씩 가지므로, 총 T개의 글자를 삽입했을 때 공간은 O(T)개의 노드이며, 각 노드는 최대 26개의 자식 링크를 저장합니다.
해시 집합 대신 트라이를 사용하는 이유는 무엇인가요?
해시 집합은 전체 단어를 조회할 때 O(L)에 답을 제공하지만, 모든 단어를 훑지 않고는 접두사에 관한 질문에 답할 수 없습니다. 모든 단어의 모든 접두사를 담는 두 번째 집합을 추가할 수도 있지만, 그러면 20글자 단어 하나에 20개의 접두사가 저장되고 그 안의 글자 수는 모두 합쳐 210개가 됩니다. 트라이는 공통 접두사를 한 번만 저장하며, 같은 순회로 두 질문 모두에 답합니다. 노드마다 배열 슬롯이 26개 있으면 접두사 아래를 순회할 때 알파벳 순서대로 단어를 만나게 되는데, 이는 자동 완성에 필요합니다.
트라이 노드는 26개의 링크가 있는 배열을 사용해야 할까요, 아니면 해시 맵을 사용해야 할까요?
배열은 글자마다 하나의 인덱스를 사용해 자식 노드를 가장 빠르게 찾을 수 있지만, 하나만 사용하는 경우에도 모든 노드가 26개의 슬롯을 차지합니다. 맵은 존재하는 자식 노드만 저장하고 어떤 알파벳에도 사용할 수 있지만, 글자마다 해싱 단계가 필요합니다. 영어 소문자 단어의 경우 어느 쪽을 사용해도 괜찮지만, 유니코드 텍스트나 희소 트라이에서는 맵을 사용하면 메모리를 많이 절약할 수 있습니다.
트라이는 실제로 어디에 사용되나요?
자동 완성 및 검색 제안 기능은 트라이에서 입력된 접두어까지 이동한 다음 그 아래에 있는 단어를 나열합니다. 맞춤법 검사기, 보드에서 사전 단어를 찾는 단어 게임, 가장 길게 일치하는 주소 접두어를 찾는 라우터도 같은 구조를 사용합니다. 여러 문자열이 같은 시작 부분을 공유하고 시작 부분으로 검색할 때마다 트라이가 적합합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def trieOps(ops, words):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
ops = ["insert", "search", "startsWith", "insert", "search"] words = ["card", "car", "car", "car", "car"]
기대값
["null", "false", "true", "null", "true"]