자동 완성
Coddy의 트라이 - 자료구조 시리즈 #8 코스 레슨 — 14개 중 12번째.
이것은 트라이(trie)의 전형적인 사용 사례입니다. 사용자가 지금까지 입력한 내용을 바탕으로, 해당 접두사로 시작하는 저장된 모든 단어를 나열합니다. 접두사 노드까지 이동합니다. 이동할 수 없다면 아무것도 반환하지 마십시오. 그런 다음 그 아래의 하위 트리를 탐색하여 찾은 모든 단어를 수집합니다.
DFS를 수행하며 아래로 내려갈 때, 방금 건넌 간선의 문자를 추가하여 단어를 점진적으로 구성합니다. isEndOfWord가 true인 노드에 도달할 때마다, 현재 경로가 일치하는 단어 중 하나가 됩니다.
챌린지
중급문자열 배열 words와 문자열 prefix를 인자로 받아, 해당 배열에서 prefix로 시작하는 단어들의 목록을 반환하는 autocomplete 함수를 작성하세요.
반환되는 목록은 반드시 오름차순(알파벳순)으로 정렬되어야 합니다. 일치하는 단어가 없으면 빈 목록을 반환하세요.
반드시 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"); }
int out_n = 0;
char** res = autocomplete(words, n, prefix, &out_n);
for (int i = 0; i < out_n; i++) { printf("%s", res[i]); if (i + 1 < out_n) printf(" "); }
printf("\n");
if (res) free(res);
return 0;
}