사전에서 가장 긴 단어
Coddy의 트라이 - 자료구조 시리즈 #8 코스 레슨 — 14개 중 13번째.
단어 사전이 주어졌을 때, 사전에 이미 있는 단어에 한 번에 한 글자씩 추가하여 만들 수 있는 가장 긴 단어를 찾으세요. "world"는 "w", "wo", "wor", 그리고 "worl"이 모두 저장된 단어인 경우에만 인정됩니다.
이것은 트라이(trie)를 사용하기에 완벽한 문제입니다. 모든 단어를 삽입한 다음, 루트에서 DFS를 수행하되, isEndOfWord로 표시된 자식 노드로만 내려가세요. 그렇게 하면 DFS 중에 방문하는 모든 노드는 모든 접두사가 그 자체로 단어인 경로를 나타내게 됩니다.
가장 긴 경로를 추적하세요. 만약 두 경로의 길이가 같다면, 사전순으로 더 작은 것을 선택하세요.
챌린지
중급문자열 배열 words를 입력받아, 배열 내의 더 짧은 단어에 한 번에 한 글자씩 추가하여 만들 수 있는 가장 긴 단어를 반환하는 함수 longestWordInDict를 작성하세요.
만약 두 단어의 길이가 같다면, 사전순으로 더 작은 단어를 반환하세요. 배열이 비어 있다면 빈 문자열을 반환하세요.
반드시 Trie 클래스(trienode와 함께 trie에 제공됨)를 사용해야 하며, 개수를 세거나 추적하기 위해 세트(sets), 딕셔너리(dicts), 맵(maps)과 같은 언어 내장 기능을 사용해서는 안 됩니다.
직접 해보기
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char line[4096];
if (!fgets(line, sizeof(line), stdin)) line[0] = 0;
line[strcspn(line, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(line, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
char* res = longestWordInDict(words, n);
printf("%s\n", res);
free(res);
return 0;
}