단어 분할
Coddy의 트라이 - 자료구조 시리즈 #8 코스 레슨 — 14개 중 14번째.
문자열 s와 단어 사전이 주어졌을 때, s를 남는 부분 없이 사전 단어들의 시퀀스로 쪼갤 수 있을까요? "leetcode"는 두 단어가 모두 사전에 있다면 "leet" + "code"로 나뉩니다. 반면 "catsandog"는 어떻게 잘라도 나뉘지 않습니다.
동적 계획법(dynamic-programming)을 사용하면 이를 해결할 수 있습니다. dp[i]를 처음 i개의 문자를 분할할 수 있는가?로 정의합니다. dp[0] = true로 시작합니다. dp[i]가 true인 모든 i에 대해, 문자열의 i 위치부터 트라이(trie)를 탐색합니다. 탐색 중 인덱스 j에서 isEndOfWord 노드에 도달할 때마다 dp[j+1] = true로 설정합니다.
트라이를 사용하면 각 탐색이 빨라집니다. 문자 하나만 일치하지 않아도 탐색이 종료되기 때문입니다. 최종 결과는 dp[n]에 저장됩니다.
챌린지
중급문자열 s와 문자열 배열 dictionary를 인자로 받아, s를 사전에 있는 하나 이상의 공백 없는 조각들로 분할할 수 있으면 true를, 그렇지 않으면 false를 반환하는 함수 wordBreak를 작성하세요.
빈 문자열 s는 항상 분할 가능한 것으로 간주합니다.
반드시 Trie 클래스(trienode와 함께 trie에 제공됨)를 사용해야 하며, 개수를 세거나 추적하기 위해 언어 내장 기능인 set, dict, map 등을 사용해서는 안 됩니다.
직접 해보기
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char s[4096], dLine[4096];
if (!fgets(s, sizeof(s), stdin)) s[0] = 0;
if (!fgets(dLine, sizeof(dLine), stdin)) dLine[0] = 0;
s[strcspn(s, "\r\n")] = '\0';
dLine[strcspn(dLine, "\r\n")] = '\0';
char* d[1024]; int dn = 0;
char* tok = strtok(dLine, " \t");
while (tok && dn < 1024) { d[dn++] = tok; tok = strtok(NULL, " \t"); }
printf("%s\n", wordBreak(s, d, dn) ? "true" : "false");
return 0;
}