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

أطول بادئة مشتركة

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

تم تصميم التحديات التالية لاستخدام Trie فيها.

استخدم فئات Trie و TrieNode التي قمت ببنائها في الدروس السابقة (يتم توفيرها لك في الملفات الموجودة على اليسار). يأتي كل تحدٍ مع ملف solution جديد حيث تكتب دالة تستخدم الـ Trie.

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

challenge icon

التحدي

سهل

اكتب دالة longestCommonPrefix تستقبل مصفوفة نصوص words وتعيد أطول نص يمثل بادئة (prefix) لكل كلمة في المصفوفة.

إذا كانت المصفوفة فارغة، أو لم تكن هناك بادئة مشتركة، فقم بإعادة سلسلة نصية فارغة.

يجب عليك استخدام فئة Trie (المتوفرة في trie مع trienode) - لا تستخدم ميزات اللغة المدمجة مثل sets أو dicts أو maps للعد أو التتبع.

جرّب بنفسك

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

int main() {
    char line[4096];
    if (!fgets(line, sizeof(line), stdin)) line[0] = 0;
    line[strcspn(line, "\r\n")] = '\0';
    char* words[1024]; int n = 0;
    char* tok = strtok(line, " \t");
    while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
    char* res = longestCommonPrefix(words, n);
    printf("%s\n", res);
    free(res);
    return 0;
}

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