عد الكلمات ببادئة
الدرس 11 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.
كم عدد الكلمات المخزنة التي تبدأ ببادئة معينة؟ بعد إدخال كل كلمة، انتقل من الجذر حرفاً واحداً في كل مرة على طول البادئة. إذا كان أي حرف مفقوداً، فإن الإجابة هي صفر - لا يمكن لأي كلمة أن تبدأ بتلك البادئة.
إذا وصلت إلى نهاية البادئة، فستستقر على عقدة. كل كلمة مخزنة تبدأ بهذه البادئة توجد في مكان ما في الشجرة الفرعية التي تبدأ من هناك. قم بعدّها من خلال الانتقال عبر الشجرة الفرعية وإضافة 1 لكل عقدة تكون فيها قيمة isEndOfWord هي true.
التحدي
سهلاكتب دالة 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;
}