أطول كلمة في القاموس
الدرس 13 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.
بناءً على قاموس من الكلمات، ابحث عن أطول كلمة يمكن بناؤها حرفاً بحرف عن طريق الإضافة إلى كلمة موجودة بالفعل في القاموس. تُحتسب "world" فقط إذا كانت كل من "w" و "wo" و "wor" و "worl" كلمات مخزنة أيضاً.
هذا مناسب تماماً لهيكل البيانات trie. أدخل كل كلمة، ثم قم بإجراء DFS من الجذر - ولكن لا تنتقل إلى عقدة فرعية إلا إذا كانت مميزة بـ isEndOfWord. بهذه الطريقة، تمثل كل عقدة نزورها أثناء DFS مساراً تكون فيه كل بادئة عبارة عن كلمة بحد ذاتها.
تتبع أطول مسار. إذا كان لمسارين نفس الطول، فاختر المسار الأصغر معجمياً.
التحدي
متوسطاكتب دالة longestWordInDict تستقبل مصفوفة من السلاسل النصية words وتعيد أطول كلمة يمكن بناؤها عن طريق إضافة حرف واحد في كل مرة إلى كلمة أقصر موجودة في المصفوفة.
إذا تساوت كلمتان في الطول، فقم بإعادة الكلمة الأصغر معجمياً. إذا كانت المصفوفة فارغة، فقم بإعادة سلسلة نصية فارغة.
يجب عليك استخدام فئة 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 = longestWordInDict(words, n);
printf("%s\n", res);
free(res);
return 0;
}