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

الإكمال التلقائي

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

هذه هي حالة الاستخدام الكلاسيكية لشجرة trie: بناءً على ما كتبه المستخدم حتى الآن، قم بسرد كل كلمة مخزنة تبدأ بتلك البادئة. انتقل إلى عقدة البادئة؛ إذا لم تتمكن من ذلك، فلا ترجع شيئاً. ثم استكشف الشجرة الفرعية الموجودة بالأسفل واجمع كل كلمة تجدها.

بينما تنتقل للأسفل أثناء عملية DFS، قم ببناء الكلمة بشكل تدريجي عن طريق إلحاق حرف الحافة التي عبرتها للتو. في كل مرة تصل فيها إلى عقدة تكون فيها قيمة isEndOfWord هي true، فإن المسار الحالي هو أحد التطابقات.

challenge icon

التحدي

متوسط

اكتب دالة autocomplete تستقبل مصفوفة سلاسل نصية words وسلسلة نصية prefix، وتعيد قائمة الكلمات من المصفوفة التي تبدأ بـ 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"); }
    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;
}

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