تقسيم الكلمات
الدرس 14 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.
بإعطاء سلسلة نصية s وقاموس من الكلمات، هل يمكننا تقسيم s إلى تسلسل من كلمات القاموس دون ترك أي شيء متبقٍ؟ تتجزأ "leetcode" إلى "leet" + "code" إذا كانت كلتاهما في القاموس؛ بينما لا تتجزأ "catsandog" بغض النظر عن كيفية تقسيمها.
تمريرة برمجة ديناميكية (dynamic-programming) تنجز المهمة. عرّف dp[i] على أنها هل يمكن تقسيم أول i من الأحرف؟ ابدأ بـ dp[0] = true. لكل i حيث تكون dp[i] صحيحة (true)، تتبع شجرة الـ trie من الموضع i في السلسلة النصية؛ وفي كل مرة ينتهي فيها التتبع عند عقدة isEndOfWord عند الفهرس j، قم بتعيين dp[j+1] = true.
تجعل الـ trie كل عملية تتبع سريعة: فحرف واحد مفقود ينهيها. الإجابة النهائية موجودة في dp[n].
التحدي
متوسطاكتب دالة wordBreak تستقبل سلسلة نصية s ومصفوفة سلاسل نصية dictionary، وتعيد true إذا كان من الممكن تقسيم s إلى قطعة واحدة أو أكثر خالية من المسافات وتكون جميعها موجودة في القاموس، أو false خلاف ذلك.
تعتبر السلسلة s الفارغة دائمًا قابلة للتقسيم.
يجب عليك استخدام فئة Trie (المتوفرة في trie مع trienode) - لا تستخدم الأدوات المدمجة في اللغة مثل المجموعات (sets) أو القواميس (dicts) أو الخرائط (maps) للعد أو التتبع.
جرّب بنفسك
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char s[4096], dLine[4096];
if (!fgets(s, sizeof(s), stdin)) s[0] = 0;
if (!fgets(dLine, sizeof(dLine), stdin)) dLine[0] = 0;
s[strcspn(s, "\r\n")] = '\0';
dLine[strcspn(dLine, "\r\n")] = '\0';
char* d[1024]; int dn = 0;
char* tok = strtok(dLine, " \t");
while (tok && dn < 1024) { d[dn++] = tok; tok = strtok(NULL, " \t"); }
printf("%s\n", wordBreak(s, d, dn) ? "true" : "false");
return 0;
}