Menu
Coddy logo textTech

השלמה אוטומטית

שיעור 12 מתוך 14 בקורס טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8 של Coddy.

זהו מקרה השימוש הקלאסי של trie: בהינתן מה שהמשתמש הקליד עד כה, הציגו את כל המילים המאוחסנות שמתחילות בקידומת הזאת. עברו אל צומת הקידומת; אם אינכם יכולים, החזירו רשימה ריקה. לאחר מכן סיירו בתת-העץ שמתחתיו ואספו כל מילה שתמצאו.

כשאתם יורדים במהלך חיפוש ה-DFS, בנו את המילה בהדרגה על ידי הוספת התו של הקשת שזה עתה עברתם בה. בכל פעם שאתם מגיעים לצומת שבו isEndOfWord הוא true, הנתיב הנוכחי הוא אחת מההתאמות.

challenge icon

אתגר

בינוני

כתבו פונקציה autocomplete שמקבלת מערך מחרוזות words ומחרוזת prefix, ומחזירה את רשימת המילים מהמערך שמתחילות ב־prefix.

הרשימה המוחזרת חייבת להיות בסדר עולה (אלפביתי). אם אין מילים מתאימות, החזירו רשימה ריקה.

חובה להשתמש במחלקה Trie (שסופקה בקובץ trie יחד עם trienode) — אין להשתמש במבנים מובנים בשפה כמו קבוצות, מילונים או מפות לצורך ספירה או מעקב.

נסו בעצמכם

#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;
}

כל השיעורים ביחידה טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8

תרגלו בעצמכם: קומפיילר C אונליין