접두사가 포함된 단어 개수 세기
Coddy의 트라이 - 자료구조 시리즈 #8 코스 레슨 — 14개 중 11번째.
주어진 접두사(prefix)로 시작하는 저장된 단어는 몇 개일까요? 모든 단어를 삽입한 후, 루트에서부터 접두사를 따라 한 번에 한 글자씩 이동합니다. 만약 어떤 글자라도 빠져 있다면, 답은 0입니다. 해당 접두사로 시작하는 단어가 존재할 수 없기 때문입니다.
접두사의 끝에 도달하면 특정 노드에 도착하게 됩니다. 이 접두사로 시작하는 모든 저장된 단어는 해당 노드를 루트로 하는 서브트리 어딘가에 존재합니다. 서브트리를 탐색하며 isEndOfWord가 true인 모든 노드에 대해 1씩 더하여 개수를 셉니다.
챌린지
쉬움문자열 배열 words와 문자열 prefix를 인자로 받아, 배열 내에서 주어진 접두사(prefix)로 시작하는 단어의 개수를 반환하는 함수 countWordsWithPrefix를 작성하세요.
빈 접두사는 모든 단어와 일치합니다.
반드시 Trie 클래스를 사용해야 합니다 (trienode와 함께 trie에 제공됨). 개수를 세거나 추적하기 위해 세트(sets), 딕셔너리(dicts), 맵(maps)과 같은 언어 내장 기능을 사용하지 마세요.
직접 해보기
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char l1[4096], prefix[1024];
if (!fgets(l1, sizeof(l1), stdin)) l1[0] = 0;
if (!fgets(prefix, sizeof(prefix), stdin)) prefix[0] = 0;
l1[strcspn(l1, "\r\n")] = '\0';
prefix[strcspn(prefix, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(l1, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
printf("%d\n", countWordsWithPrefix(words, n, prefix));
return 0;
}