مسافة التحرير خطوةً بخطوة
الإدراج والحذف والاستبدال للتحويل
مسافة التحرير خطوةً بخطوة درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ما الذي تقيسه مسافة التحرير
مسافة التحرير هي أقل عدد من عمليات التحرير على محارف مفردة لتحويل سلسلة نصوص إلى أخرى. وهي تقيس مدى اختلاف كلمتين فعليًا.
العمليات الثلاث
يمكنك إدراج محرف واحد أو حذفه أو استبداله في كل عملية تحرير. وتبلغ تكلفة كل عملية واحدًا بالضبط في المسألة القياسية.
حدّد الحالة
لتكن dp[i][j] عدد عمليات التحرير اللازمة لتحويل أول i محرفًا من A إلى أول j محرفًا من B.
التطابق المجاني
إذا كان المحرفان الحاليان متطابقين أصلًا، فلا حاجة إلى أي عملية تحرير. ما عليك سوى نقل قيمة القطر مباشرةً إلى الأسفل.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]وإلا، ادفع واحدًا
عندما يختلف المحرفان، اختر الجار الأقل تكلفة وأضف عملية تحرير واحدة. يغطي هذا الأسلوب، min زائد واحد، العمليات الثلاث كلها.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])ما دلالة كل جار
الخلية الموجودة فوقك تعني الحذف، والخلية الموجودة إلى اليسار تعني الإدراج، والخلية القطرية تعني الاستبدال. وتختار min الخيار الأقل تكلفة فحسب.
الحالات الأساسية للسلسلة الفارغة
يتطلب تحويل سلسلة طولها i إلى سلسلة فارغة حذف i محرفًا. لذلك املأ الصف والعمود الأولين بالقيم 0 و1 و2 وهكذا.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jحدّد حجم الجدول
استخدم شبكة بحجم n+1 by m+1 حتى تحصل البادئات الفارغة على صف وعمود خاصين بهما. يحافظ هذا الحشو على بساطة الحلقات.
dp = [[0] * (m+1) for _ in range(n+1)]املأه بالترتيب
كرّر على i وj تصاعديًا بدءًا من 1. تعتمد كل خلية فقط على الجيران المملوءين مسبقًا فوقها وعن يسارها وعلى قطرها.
for i in range(1, n+1):
for j in range(1, m+1):
...اقرأ المسافة
ينتهي أقل عدد من عمليات التحرير في الزاوية. تكون الإجابة هي dp[n][m] بعد اكتمال الجدول.
distance = dp[n][m]التكلفة والتنويعات
يعمل هذا في O(n times m) من الوقت. قد تفرض المهام الواقعية تكاليف مختلفة لكل عملية، لكن العلاقة التكرارية نفسها تظل صالحة.
تحقّق سريع
المحرفان A[i-1] وB[j-1] مختلفان. أي علاقة تكرارية تعطي مسافة التحرير؟
مراجعة: مسافة التحرير
يعني التطابق نقل قيمة القطر، بينما يعني عدم التطابق إضافة 1 إلى أصغر ثلاثة جيران. هيّئ الحدود، واقرأ dp[n][m]. ✏️
الأسئلة الشائعة
هل درس «مسافة التحرير خطوةً بخطوة» مجاني؟
نعم — نص درس «مسافة التحرير خطوةً بخطوة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «مسافة التحرير خطوةً بخطوة»؟
الإدراج والحذف والاستبدال للتحويل تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «مسافة التحرير خطوةً بخطوة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- عدّ المسارات على شبكة
- أقل مجموع لمسار مع العوائق
- أطول تتابع مشترك
- مسافة التحرير خطوةً بخطوة