الإكمال التلقائي
الدرس 12 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.
هذه هي حالة الاستخدام الكلاسيكية لشجرة trie: بناءً على ما كتبه المستخدم حتى الآن، قم بسرد كل كلمة مخزنة تبدأ بتلك البادئة. انتقل إلى عقدة البادئة؛ إذا لم تتمكن من ذلك، فلا ترجع شيئاً. ثم استكشف الشجرة الفرعية الموجودة بالأسفل واجمع كل كلمة تجدها.
بينما تنتقل للأسفل أثناء عملية DFS، قم ببناء الكلمة بشكل تدريجي عن طريق إلحاق حرف الحافة التي عبرتها للتو. في كل مرة تصل فيها إلى عقدة تكون فيها قيمة isEndOfWord هي true، فإن المسار الحالي هو أحد التطابقات.
التحدي
متوسطاكتب دالة 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;
}