חלוקת מילה
שיעור 14 מתוך 14 בקורס טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8 של Coddy.
בהינתן מחרוזת s ומילון של מילים, האם אפשר לחלק את s לרצף של מילים מהמילון בלי שיישאר דבר? אפשר לחלק את "leetcode" ל־"leet" + "code" אם שתיהן מופיעות במילון; אי אפשר לחלק את "catsandog", בלי קשר לאופן שבו נחתוך אותה.
מעבר של תכנות דינמי עושה את העבודה. נגדיר את dp[i] בתור האם אפשר לחלק למקטעים את i התווים הראשונים? נתחיל עם dp[0] = true. עבור כל i שעבורו dp[i] הוא true, נתקדם בטרייה החל מהמיקום i במחרוזת; בכל פעם שההתקדמות מגיעה לצומת isEndOfWord באינדקס j, נקבע את dp[j+1] = true.
הטרייה הופכת כל התקדמות למהירה: תו חסר אחד עוצר אותה. התשובה הסופית נמצאת ב־dp[n].
אתגר
בינוניכתבו פונקציה wordBreak שמקבלת מחרוזת s ומערך מחרוזות dictionary, ומחזירה true אם ניתן לפצל את s לחלק אחד או יותר ללא רווחים, שכל אחד מהם מופיע במילון, או false אחרת.
תמיד ניתן לפצל s ריקה.
חובה להשתמש במחלקה Trie (המסופקת ב-trie יחד עם trienode) — אין להשתמש במבנים מובנים בשפה כמו sets, dicts או maps לצורך ספירה או מעקב.
נסו בעצמכם
#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;
}
כל השיעורים ביחידה טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8
תרגלו בעצמכם: קומפיילר C אונליין