Menu
Coddy logo textTech

מתחיל ב־

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

כל הסיבה לקיומם של עצי Trie היא לענות במהירות על שאלות לגבי תחיליות. startsWith בודקת אם מילה כלשהי שנשמרה מתחילה בתחילית נתונה — לא משנה אם התחילית עצמה היא מילה שלמה שהוכנסה.

המעבר כמעט זהה ל־search: מתחילים מהשורש ועוקבים אחר הילדים, תו אחד בכל פעם. אם תו חסר בדרך, אף מילה שנשמרה לא מתחילה בתחילית הזו, ולכן מחזירים false. אם עוברים על כל התווים בלי לעצור, התשובה היא true — תת־העץ שמתחת לצומת הזה מכיל לפחות מילה אחת שנשמרה.

ההבדל היחיד מ־search: אין בדיקה של isEndOfWord בסוף. מספיק להגיע לסוף התחילית.

challenge icon

אתגר

קל

הוסף מתודה startsWith למחלקה Trie.

היא מקבלת מחרוזת prefix ומחזירה:

  • true אם מילה כלשהי שהוכנסה מתחילה ב־prefix (התחילית יכולה להתאים למילה שלמה או להיות החלק המוביל של מילה ארוכה יותר).
  • false אחרת.

נסו בעצמכם

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"

int main() {
    Trie t;
    Trie_init(&t);
    char line[1024];
    while (fgets(line, sizeof(line), stdin)) {
        line[strcspn(line, "\r\n")] = '\0';
        char* cmd = strtok(line, " \t");
        if (!cmd) continue;
        if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
        if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
        if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
        if (strcmp(cmd, "search") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_search(&t, arg) ? "true" : "false"); }
        if (strcmp(cmd, "startsWith") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_startsWith(&t, arg) ? "true" : "false"); }
    }
    return 0;
}

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

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