StartsWith
Coddy의 트라이 - 자료구조 시리즈 #8 코스 레슨 — 14개 중 7번째.
트라이(trie)가 존재하는 주된 이유는 접두사 관련 질문에 빠르게 답하기 위해서입니다. startsWith는 저장된 단어 중 어떤 것이라도 주어진 접두사로 시작하는지 확인합니다. 해당 접두사 자체가 삽입된 완전한 단어인지는 상관하지 않습니다.
탐색 과정은 search와 거의 동일합니다. 루트에서 시작하여 한 번에 한 문자씩 자식 노드를 따라갑니다. 도중에 문자가 없다면 해당 접두사로 시작하는 저장된 단어가 없다는 뜻이므로 false를 반환합니다. 멈추지 않고 모든 문자를 통과했다면 결과는 true입니다. 해당 노드 아래의 서브트리에 최소 하나 이상의 저장된 단어가 포함되어 있다는 의미입니다.
search와의 유일한 차이점은 마지막에 isEndOfWord 확인 절차가 없다는 것입니다. 접두사의 끝에 도달하는 것만으로 충분합니다.
챌린지
쉬움Trie 클래스에 startsWith 메서드를 추가하세요.
이 메서드는 문자열 prefix를 인자로 받아 다음을 반환합니다:
- 삽입된 단어 중
prefix로 시작하는 단어가 있으면true를 반환합니다 (접두사는 전체 단어와 일치하거나 더 긴 단어의 앞부분일 수 있습니다). - 그렇지 않으면
false를 반환합니다.
직접 해보기
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
if (strcmp(cmd, "search") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_search(&t, arg) ? "true" : "false"); }
if (strcmp(cmd, "startsWith") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_startsWith(&t, arg) ? "true" : "false"); }
}
return 0;
}