Edit Distance
لديك كلمتان، word1 وword2. يغيّر التعديل word1 بإحدى ثلاث طرق: إدراج حرف في أي موضع، أو حذف حرف، أو استبدال حرف بحرف آخر مختلف. أرجِع أقل عدد من التعديلات اللازمة لتحويل word1 إلى word2.
الدالة
- word1string
- الكلمة التي تعدّلها
- word2string
- الكلمة to reach
- تُرجعinteger
- أقل عدد من عمليات الإدراج والحذف والاستبدال التي تحوّل word1 إلى word2
القيود
1 ≤ word1.length ≤ 5001 ≤ word2.length ≤ 500- تحتوي كلتا الكلمتين على أحرف إنجليزية صغيرة فقط.
أمثلة
- المدخلات
- word1 = "spot"word2 = "stop"
- المخرجات
- 2
- الشرح
- استبدل p بـ t وt بـ p: تصبح
spotstot، ثمstop. تعديل واحد لا يكفي، لأن الكلمتين تختلفان في موضعين، كما أن الإدراج أو الحذف سيغيّر الطول.
- المدخلات
- word1 = "garden"word2 = "ardent"
- المخرجات
- 2
- الشرح
- احذف g لتحصل على
arden، ثم أدرج t في النهاية لتحصل علىardent. سيكلف استبدال حرف بحرف 6، لأن الكلمتين تختلفان في كل موضع.
- المدخلات
- word1 = "rain"word2 = "shine"
- المخرجات
- 3
- الشرح
- استبدل r بـ s وa بـ h، ثم أدرج e. يفشل تعديلان: فالحرفان r وa غير موجودين في
shine، لذا يحتاج كل منهما إلى تعديل يحافظ على الطول، ويجب أن تظل الكلمة أطول بحرف واحد.
سؤال إضافي
هل يمكنك أيضًا إرجاع قائمة واحدة بأقصر التعديلات، إلى جانب عددها؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
انظر إلى الحرف الأخير من كل كلمة. إذا كانا متطابقين، فهل تحتاج إلى تعديلهِما؟ وإذا اختلفا، فما التعديلات التي يمكن أن تجعل الكلمتين تنتهيان بالطريقة نفسها؟
هناك ثلاثة خيارات للحرفين الأخيرين المختلفين: استبدال أحدهما بالآخر، أو حذف الحرف الأخير من
word1، أو إدراج الحرف الأخير منword2. يترك كل خيار المشكلة نفسها على بادئات أقصر، لذا اختر الأقل تكلفة وأضف واحدًا.خزّن الإجابة لكل زوج من أطوال البادئات
(i, j)في جدول. تتطلب البادئة الفارغةiعمليات حذف أوjعمليات إدراج، وهذا يملأ الصف والعمود الأولين. املأ بقية الجدول صفًا تلو الآخر، ثم اقرأ الإجابة من الخلية الأخيرة.
الحل
تتفاعل التعديلات: تختلف garden وardent في المواضع الستة كلها، ومع ذلك يكفي تعديلان. لذا انظر إلى الحرف الأخير من كل كلمة. إما أن الحرفين متطابقان، أو أن أحد التعديلات الثلاثة يجعلهما متطابقين، وكل اختيار يترك المشكلة نفسها على بادئات أقصر. يحلّ الجدول كل زوج من البادئات مرة واحدة.
جرّب التعديلات الثلاثة باستخدام الاستدعاء الذاتي
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
لتكن edits(i, j) أقل عدد من التعديلات اللازمة لتحويل لاحقة word1[i:] إلى word2[j:]. إذا تطابق الحرفان الأولان، فأبقِهما وحرّك كلا الفهرسين: إنفاق تعديل على حرف متطابق لا يفيد أبدًا. وإلا، فأضف 1 إلى أقل تكلفة من ثلاثة استدعاءات: الاستبدال يحرّك كلا الفهرسين، وحذف word1[i] يحرّك i، وإدراج word2[j] يحرّك j. عندما تنفد حروف إحدى الكلمتين، تكلّف كل حرف متبقٍ في الأخرى تعديلًا واحدًا.
يبدأ كل اختلاف ثلاثة استدعاءات: كلمتان من 15 حرفًا لا تتشاركان أي حرف تتطلبان نحو 6.7 × 10^10 استدعاء. ومع ذلك، لا يوجد سوى (n+1) × (m+1) زوجًا مختلفًا من (i, j)، لذا فإن كل استدعاء تقريبًا يكرر استدعاءً سابقًا.
الخوارزمية
- إذا تجاوز
iنهايةword1، فأعِدm - j؛ وإذا تجاوزjنهايةword2، فأعِدn - i. - إذا كان
word1[i] == word2[j]، فأعِدedits(i+1, j+1). - وإلا فأعِد
1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)). - الإجابة هي
edits(0, 0).
def minDistance(word1, word2):
n, m = len(word1), len(word2)
def edits(i, j):
# Fewest edits to turn word1[i:] into word2[j:]
if i == n:
return m - j # insert the rest of word2
if j == m:
return n - i # delete the rest of word1
if word1[i] == word2[j]:
return edits(i + 1, j + 1)
return 1 + min(edits(i + 1, j + 1), # replace word1[i] with word2[j]
edits(i + 1, j), # delete word1[i]
edits(i, j + 1)) # insert word2[j]
return edits(0, 0)املأ جدول البادئات
الفكرة
لتكن dp[i][j] أقل عدد من التعديلات اللازمة لتحويل الأحرف i الأولى من word1 إلى الأحرف j الأولى من word2. إذا كان word1[i-1] يساوي word2[j-1]، فانقل قيمة الخانة القطرية dp[i-1][j-1]. وإلا فأضف 1 إلى أصغر قيمة بين الخانات المجاورة: الخانة القطرية تمثل استبدالًا، والخانة أعلاه تمثل حذف word1[i-1]، والخانة إلى اليسار تمثل إدراج word2[j-1]. الصف والعمود الأساسيان ليسا أصفارًا: فتحويل i أحرف إلى لا شيء يتطلب i عمليات حذف، لذا dp[i][0] = i، وبالمثل dp[0][j] = j.
بالنسبة إلى تحويل spot إلى stop، يكون الصف الأخير [4, 3, 2, 2, 2]. تقارن الخانة الأخيرة بين t وp؛ قيمتها القطرية (تحويل spo إلى sto) هي 1، وقيمتا الخليتين المجاورتين الأخريين هما 2، لذا تكون الإجابة 1 + 1 = 2. يملأ كلمتان طول كل منهما 500 حرف 2.5 × 10^5 خلية، ويُحسب كل منها في زمن ثابت.
الخوارزمية
- أنشئ
dpباستخدام(n+1) × (m+1)خلية، واجعلdp[i][0] = iوdp[0][j] = j. - لكل
iمن 1 إلىnولكلjمن 1 إلىm: إذا كانword1[i-1] == word2[j-1]، فاجعلdp[i][j] = dp[i-1][j-1]. - وإلا، فاجعل
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]). - أعِد
dp[n][m].
def minDistance(word1, word2):
n, m = len(word1), len(word2)
# dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i # delete all i letters
for j in range(m + 1):
dp[0][j] = j # insert all j letters
for i in range(1, n + 1):
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j - 1], # replace
dp[i - 1][j], # delete word1[i-1]
dp[i][j - 1]) # insert word2[j-1]
return dp[n][m]أبقِ صفَّين فقط
الفكرة
يقرأ الصف i الصف i-1 فقط وخلاياه هو الواقعة إلى اليسار، لذا يكفي استخدام مصفوفتين: prev للصف المكتمل وcur للصف الذي تملؤه. القطر هو prev[j-1]، والذي فوقه هو prev[j]، والذي إلى اليسار هو cur[j-1]. أصبح العمود الأساسي موجودًا الآن في أول خانة من كل صف، لذا عيّن cur[0] = i قبل ملء الصف i.
يتطلب تحويل word2 إلى word1 العدد نفسه من التعديلات، لأن عمليات الإدراج والحذف تتبادل الأدوار. بدّل الكلمتين كي تمتد الصفوف على طول الكلمة الأقصر: min(n, m) + 1 عددًا في كل صف بدلًا من جدول يصل حجمه إلى 251,001 خانة، مع الحفاظ على مقدار العمل نفسه O(n × m).
الخوارزمية
- إذا كان
word2أطول منword1، فبدّلهما. - عيّن
prev = [0, 1, ..., m]. - لكل
iمن 1 إلىn، عيّنcur[0] = iواملأcur[1..m]باستخدام قاعدة الجدول، مع قراءة القيم القطرية والتي في الأعلى منprev، والقيمة التي على اليسار منcur. ثم بدّلprevوcur. - أعِد
prev[m].
def minDistance(word1, word2):
if len(word2) > len(word1):
word1, word2 = word2, word1 # the rows run along the shorter word
m = len(word2)
# prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
prev = list(range(m + 1))
for i in range(1, len(word1) + 1):
cur = [i] + [0] * m # i letters into an empty prefix: delete them all
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j - 1], # replace
prev[j], # delete word1[i-1]
cur[j - 1]) # insert word2[j-1]
prev = cur
return prev[m]
أخطاء شائعة وحالات حدّية
- ملء الصف 0 والعمود 0 بالأصفار، كما في أطول تتابع مشترك. تحويل
abcإلى بادئة فارغة يكلّف 3 عمليات حذف، وليس 0. - نسيان
cur[0] = iفي نسخة الصفّين. يحتفظ المدخل الأول بقيمة من صفّين سابقين، وتكون كل خلية بعده خاطئة. - احتساب كلفة تعديل عند تطابق الحرفين. باستخدام
1 + min(...)للحروف المتساوية، فإن تحويلaإلىaيكلّف 1. - قراءة الخانة المجاورة على اليسار من
prevبدلًا منcur. الخانة على اليسار تمثل إدراجword2[j-1]في الصف الحالي. - استخدام الاستدعاء الذاتي مع التخزين المؤقت في Python لكلمات طولها 500 حرف. يصل عمق الاستدعاءات إلى 1000، متجاوزًا حدّ التكرار الافتراضي.
أسئلة شائعة3
ما هو التعقيد الزمني لمسافة التحرير؟
يملأ حلّ الجدول خلية واحدة لكل زوج من البادئات في زمن ثابت: زمن O(n × m) للطولين n وm. ويستخدم O(n × m) من الذاكرة للجدول الكامل، أو O(min(n, m)) باستخدام صفّين. أما الاستدعاء الذاتي البسيط دون جدول فزمنه أُسّي.
هل مسافة التحرير هي نفسها مسافة ليفنشتاين؟
هذه النسخة هي مسافة ليفنشتاين: تكلفة كلٍّ من الإدراج والحذف والاستبدال واحدة. ومسافة التحرير هي الاسم العام للعائلة. الاقتصار على الإدراج والحذف يعطي n + m - 2 × LCS، والاقتصار على الاستبدال مع تساوي الطولين يعطي مسافة هامينغ، وإضافة تبديل حرفين متجاورين تعطي نسخة داميرو.
هل يمكن حل مسافة التحرير باستخدام مصفوفة واحدة؟
نعم. املأ مصفوفة واحدة row في مكانها، من اليسار إلى اليمين. قبل أن تستبدل row[j]، تظل تحمل القيمة من الصف السابق، بينما تحتوي row[j-1] بالفعل على قيمة الصف الحالي. القطر وحده هو الذي يُفقَد، لذا احفظ القيمة القديمة لـ row[j] في متغير واستخدمها كقيمة القطر لـ j + 1.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def minDistance(word1, word2):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
word1 = "spot" word2 = "stop"
الإخراج المتوقع
2