Implement Trie (Prefix Tree)
소문자 단어를 위한 트라이(접두사 트리)를 만들고 세 가지 연산을 구현하세요. insert w는 단어 w를 추가하고, search w는 w 자체가 삽입되었는지 알려 주며, startsWith p는 삽입된 단어 중 p로 시작하는 단어가 있는지 알려 줍니다. 단어는 자기 자신의 접두사로 간주됩니다.
연산 i는 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"]
- 설명
car는card로 시작하므로startsWith car는"true"이지만,car는 삽입된 적이 없으므로 첫 번째 검색 결과는"false"입니다.insert 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로 시작하지만 어느 것도 정확히te는 아니므로, startsWith는"true"이고 검색은"false"입니다.tex로 시작하는 단어는 없으며,tea는 자기 자신의 접두사입니다.
- 입력
- ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
- 출력
- ["false", "false", "null", "true", "false", "true"]
- 설명
- 빈 트라이에서는 두 쿼리 모두
"false"입니다.insert dog를 수행한 후 검색하면 dog를 찾고,dogs로 시작하는 단어는 없으며,do는dog의 시작 부분입니다.
후속 질문
여전히 O(L) 시간에 저장된 서로 다른 단어 중 p로 시작하는 단어의 개수를 반환하는 countPrefix p 연산을 어떻게 추가할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
전체 단어 집합은 한 번의 조회로
search에 답할 수 있지만, 각 단어를 하나씩 확인하지 않고는 어떤 단어가te로 시작하는지 알 수 없습니다. 같은 방식으로 시작하는 단어들이 그 시작 부분의 저장 공간을 공유한다면 어떨까요?모든 노드가 접두사를 나타내고, 다음에 올 수 있는 각 문자마다 자식 링크를 하나씩 가지는 트리를 만드세요. 그러면 단어는 루트에서 시작하는 경로가 됩니다. 각 노드에 저장된 단어가 정확히 그 지점에서 끝나는지를 나타내는 플래그를 지정하세요.
각 연산은 루트에서 시작해 글자들을 따라갑니다.
insert는 누락된 노드를 만들고 마지막 노드에 플래그를 설정합니다.startsWith는 따라가기가 끝에 도달하면 성공하고,search는 멈춘 노드에 플래그가 설정되어 있어야 합니다.
풀이
해시 집합은 search에 답할 수 있지만, 시작에 대한 개념이 없으므로 startsWith는 모든 단어를 살펴보게 됩니다. 트라이는 각 단어를 루트에서 시작하는 문자 경로로 저장합니다. 같은 문자로 시작하는 단어는 경로를 공유하고, 플래그는 저장된 단어가 끝나는 위치를 표시합니다. 두 질의 모두 최대 L개의 링크를 따라 한 번 이동하면 됩니다.
단어 목록을 유지하고 이를 검색합니다
핵심 아이디어
삽입된 모든 단어를 목록에 보관하세요. search w는 w를 저장된 각 단어와 비교하고, startsWith p는 저장된 단어 중 p로 시작하는 단어가 있는지 확인합니다. 정의를 직접 검사하므로 올바른 방법입니다. 저장된 단어가 n개일 때 각 쿼리는 최대 L개의 문자로 이루어진 비교를 최대 n번 수행합니다. 단어 1,000개와 쿼리 1,000개라면 문자열 비교가 100만 번 이루어집니다.
알고리즘
- 빈 목록으로 시작합니다.
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가 있습니다. tea를 삽입하면 t, te, tea에 해당하는 노드가 생성됩니다. 그런 다음 ten을 삽입하면 두 단어가 te까지의 경로를 공유하므로 ten에 해당하는 노드만 추가됩니다.
순회 중 링크가 없다는 것을 발견하면 해당 글자로 시작하는 저장된 단어가 없다는 뜻입니다. tex는 te에서 멈추는데, 여기에 x 링크가 없기 때문입니다. 순회가 끝에 도달하면 질의에 해당하는 노드에 도착한 것이므로 startsWith는 true이고, search는 플래그에 따라 답을 반환합니다. te에 해당하는 노드는 존재하지만 플래그가 꺼져 있으므로 search te는 false입니다. 저장된 단어가 몇 개든 각 연산은 최대 L개의 링크를 따라가며, 트라이에는 서로 다른 접두사마다 노드가 하나씩 있습니다.
알고리즘
- 자식 링크가 없고
isEnd가 꺼진 루트를 만듭니다. insert w: 루트에서 각 문자에 해당하는 링크를 따라가고, 링크가 없으면 노드를 만듭니다. 마지막 노드의isEnd를 켭니다.find(p): 루트에서 각 문자에 해당하는 링크를 따라갑니다. 하나라도 없으면 즉시 아무것도 반환하지 않고, 그렇지 않으면 도달한 노드를 반환합니다.search w:find(w)가isEnd가 설정된 노드를 반환하면 true입니다.startsWith p:find(p)가 노드를 반환하면 true입니다.
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를 반환하도록 하는 것.insert card뒤에는car의 경로가 존재하지만,search car는 false여야 합니다. - 새로 생성된 노드에만
isEnd를 설정하는 것.cards뒤에card를 삽입해도 아무것도 생성되지 않지만, 마지막 노드에는 플래그가 필요합니다. - 링크가 이미 존재하는데 새 자식을 생성하는 것. 새
t노드와 함께ten을 삽입하면tea가 사라집니다. - 경로의 끝을 지나서 읽는 것.
sun만 저장된 상태에서startsWith sunny를 실행하면 첫 번째 링크가 없는 지점에서 멈추고 false를 반환해야 합니다.
자주 묻는 질문3
트라이의 시간 복잡도는 얼마인가요?
삽입, 검색 및 startsWith는 각각 글자마다 하나의 링크를 따라가므로, 저장된 단어 수와 관계없이 길이가 L인 단어에 대해 각각 O(L)의 시간이 걸립니다. 공간은 총 T개의 삽입된 글자에 대해 O(T)개의 노드가 필요하며, 각 노드는 최대 26개의 자식 링크를 가집니다.
해시 집합 대신 트라이를 사용하는 이유는 무엇인가요?
해시 집합은 O(L) 시간에 전체 단어를 찾지만, 모든 단어를 훑지 않고는 접두사에 관한 질문에 답할 수 없습니다. 모든 접두사를 두 번째 집합에 저장하면 20글자 단어 하나에 210글자가 필요합니다. 트라이는 공유되는 각 접두사를 한 번만 저장하며, 한 번의 탐색으로 두 질문에 모두 답합니다.
트라이 노드는 26개의 링크가 있는 배열을 사용해야 할까요, 아니면 해시 맵을 사용해야 할까요?
배열은 하나의 인덱스로 자식을 찾지만, 자식이 하나뿐인 노드에도 노드당 슬롯 26개가 필요합니다. 맵은 존재하는 자식만 저장하고 어떤 알파벳에도 사용할 수 있지만, 문자마다 해시를 계산해야 합니다. 영어 소문자에는 둘 다 사용할 수 있으며, 유니코드나 희소 트라이에서는 맵이 메모리를 절약합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def trieOps(ops, words):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
ops = ["insert", "search", "startsWith", "insert", "search"] words = ["card", "car", "car", "car", "car"]
예상 출력
["null", "false", "true", "null", "true"]