أطول تتابع مشترك
محاذاة سلسلتين باستخدام جدول برمجة ديناميكية
أطول تتابع مشترك درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ما هو التسلسل الجزئي
يحافظ التسلسل الجزئي على ترتيب المحارف، لكنه قد يتخطى بعضها. من 'abcde' يمكنك اختيار 'ace'، لكن لا يمكنك اختيار 'aec' مطلقًا.
هدف LCS
عند إعطائك سلسلتي نصوص، يكون أطول تسلسل جزئي مشترك هو أطول تسلسل يظهر في كلتيهما بالترتيب النسبي نفسه.
انتقل إلى شبكة
قارن البادئات في سلسلتي النصوص. يحوّل جدول ثنائي الأبعاد يمتد على طولهما هذه المسألة إلى DP شبكية مألوفة.
حدّد الحالة
لتكن dp[i][j] طول LCS لأول i محرفًا من A ولأول j محرفًا من B.
عندما تتطابق المحارف
إذا كان A[i-1] مساويًا لـ B[j-1]، فإن المحرف المشترك يمدد LCS. أضف واحدًا إلى قيمة القطر dp[i-1][j-1].
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1عندما تختلف المحارف
إذا اختلف المحرفان، احذف محرفًا واحدًا من إحدى السلسلتين واحتفظ بالنتيجة الأفضل. خذ قيمة max للجارين.
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])الحالة الأساسية
لا تشترك أي بادئة فارغة في محارف، لذلك يكون طول LCS مساويًا للصفر. يظل الصف 0 والعمود 0 ممتلئين بـالأصفار.
dp = [[0] * (m+1) for _ in range(n+1)]صف وعمود إضافيان
إنشاء الجدول بحجم n+1 by m+1 يمنحك حدًا صفريًا مجانيًا. ويزيل ذلك فحوصات الحدود المزعجة عند الحواف.
املأه بالكامل
كرّر على i وj بدءًا من 1 تصاعديًا. تحتاج كل خلية فقط إلى القيم الموجودة فوقها وعن يسارها وعلى قطرها، وقد تم حسابها مسبقًا.
for i in range(1, n+1):
for j in range(1, m+1):
...اقرأ الطول
يوجد طول LCS الكامل في الزاوية. تكون الإجابة هي dp[n][m] بعد ملء كل الخلايا.
length = dp[n][m]التعقيد
تلمس كل خلية مرة واحدة، لذلك يستغرق التنفيذ O(n times m) من الوقت والذاكرة. وهذا يتعامل بسهولة مع سلاسل يصل طولها إلى بضعة آلاف من المحارف.
تحقّق سريع
المحرفان الحاليان A[i-1] وB[j-1] متساويان. ما التحديث الصحيح؟
مراجعة: LCS
أنشئ جدولًا بحجم n+1 by m+1: عند التطابق أضف واحدًا إلى القطر، وإلا فخذ قيمة الجار الأكبر. تحتوي الزاوية على الطول. 🔗
الأسئلة الشائعة
هل درس «أطول تتابع مشترك» مجاني؟
نعم — نص درس «أطول تتابع مشترك» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «أطول تتابع مشترك»؟
محاذاة سلسلتين باستخدام جدول برمجة ديناميكية تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «أطول تتابع مشترك»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.