המילה הארוכה ביותר במילון
שיעור 13 מתוך 14 בקורס טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8 של Coddy.
בהינתן מילון של מילים, מצאו את המילה הארוכה ביותר שאפשר לבנות תו אחד בכל פעם על ידי הוספת תווים למילה שכבר נמצאת במילון. "world" נחשבת רק אם גם "w", "wo", "wor" וגם "worl" שמורות כמילים.
טרייה מתאימה לכך באופן מושלם. הכניסו כל מילה, ואז בצעו DFS מהשורש — אבל רדו לצומת ילד רק אם הוא מסומן isEndOfWord. כך, כל צומת שבו נבקר במהלך ה-DFS מייצג מסלול שבו כל קידומת היא בעצמה מילה.
עקבו אחר המסלול הארוך ביותר. אם לשני מסלולים יש אותו אורך, בחרו במסלול הקטן יותר בסדר לקסיקוגרפי.
אתגר
בינוניכתבו פונקציה longestWordInDict שמקבלת מערך מחרוזות words ומחזירה את המילה הארוכה ביותר שאפשר לבנות על ידי הוספת תו אחד בכל פעם למילה קצרה יותר במערך.
אם שתי מילים שוות באורכן, החזירו את המילה הקטנה יותר בסדר לקסיקוגרפי. אם המערך ריק, החזירו מחרוזת ריקה.
חובה להשתמש במחלקה Trie (שניתנת בקובץ trie יחד עם trienode) — אין להשתמש במבנים המובנים בשפה, כגון קבוצות, מילונים או מפות, לצורך ספירה או מעקב.
נסו בעצמכם
#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;
}
כל השיעורים ביחידה טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8
3אתגרי תרגול
הקידומת המשותפת הארוכה ביותרספירת מילים עם קידומתהשלמה אוטומטיתהמילה הארוכה ביותר במילוןחלוקת מילהתרגלו בעצמכם: קומפיילר C אונליין