Menu
Coddy logo textTech
flag Ar iconالعربيةdown icon

يبدأ بـ

الدرس 7 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.

السبب الكامل لوجود هياكل الـ tries هو الإجابة على أسئلة البادئات (prefix) بسرعة. تتحقق startsWith مما إذا كانت أي كلمة مخزنة تبدأ ببادئة معينة - ولا يهم ما إذا كانت تلك البادئة نفسها كلمة كاملة تم إدخالها أم لا.

عملية الانتقال (the walk) مطابقة تقريبًا لـ search: من الجذر (root)، اتبع الأبناء حرفًا واحدًا في كل مرة. إذا كان هناك حرف مفقود في الطريق، فهذا يعني أنه لا توجد كلمة مخزنة تبدأ بتلك البادئة، لذا قم بإرجاع false. إذا مررت عبر كل حرف دون توقف، فستكون الإجابة true - حيث تحتوي الشجرة الفرعية (subtree) الموجودة أسفل تلك العقدة على كلمة مخزنة واحدة على الأقل.

الاختلاف الوحيد عن 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;
}

جميع دروس Tries - سلسلة هياكل البيانات #8