Menu
Coddy logo textTech

ספירת מילים עם קידומת

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

כמה מילים שמורות מתחילות בקידומת נתונה? לאחר הוספת כל מילה, מתקדמים מהשורש תו אחד בכל פעם לאורך הקידומת. אם תו כלשהו חסר, התשובה היא אפס — אף מילה לא יכולה להתחיל בקידומת הזו.

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

challenge icon

אתגר

קל

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

קידומת ריקה מתאימה לכל מילה.

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

נסו בעצמכם

#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"); }
    printf("%d\n", countWordsWithPrefix(words, n, prefix));
    return 0;
}

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

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