أطول بادئة مشتركة
الدرس 10 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.
تم تصميم التحديات التالية لاستخدام Trie فيها.
استخدم فئات Trie و TrieNode التي قمت ببنائها في الدروس السابقة (يتم توفيرها لك في الملفات الموجودة على اليسار). يأتي كل تحدٍ مع ملف solution جديد حيث تكتب دالة تستخدم الـ Trie.
مشكلتنا الأولى: بناءً على قائمة من الكلمات، ابحث عن أطول بادئة مشتركة تتشاركها جميعاً. بعد إدخال كل كلمة في trie، تكون الإجابة هي المسار من الجذر إلى الأسفل طالما يوجد طفل واحد بالضبط في كل خطوة ولا توجد عقدة تمثل نهاية الكلمة.
التحدي
سهلاكتب دالة 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;
}