Edit Distance

Q: ما هو التعقيد الزمني لمسافة التحرير؟

يعمل حل الجدول في زمن O(n × m) ، حيث يمثّل n و m الطولين، لأنه يملأ خلية واحدة لكل زوج من البوادئ بعمل ثابت. ويستخدم ذاكرة O(n × m) للجدول الكامل، أو O(min(n, m)) باستخدام صفّين. أما الاستدعاء الذاتي البسيط دون جدول فزمنه أُسّي.

Q: كيف تحصل على قائمة التعديلات، وليس على عددها فقط؟

احتفظ بالجدول كاملًا، ثم ارجع منه بدءًا من dp[n][m] . إذا تطابقت الحروف، فتحرّك قطريًا من دون إجراء أي تعديل. وإلا، فانتقل إلى الخانة المجاورة التي تقل قيمتها بمقدار واحد: الانتقال قطريًا يعني الاستبدال، والانتقال إلى الأعلى يعني الحذف، والانتقال إلى اليسار يعني الإدراج. توقّف عند dp[0][0] ، واقرأ التعديلات بترتيب عكسي. لا يمكن لإصدار الصفّين إجراء ذلك بمفرده، لأنه تخلّص من الصفوف السابقة.

Q: هل يمكن حل مسافة التحرير باستخدام مصفوفة واحدة؟

نعم. املأ مصفوفة واحدة row في مكانها، من اليسار إلى اليمين. قبل أن تستبدل row[j] ، تظل تحتوي على القيمة من الصف السابق، بينما يحتوي row[j-1] بالفعل على قيمة الصف الحالي. القيمة الوحيدة التي تفقدها هي القيمة القطرية، لذا احتفظ بها في متغير: احفظ قيمة row[j] القديمة قبل الكتابة، واستخدمها كقيمة قطرية لـ j + 1 .

صعبالبرمجة الديناميكية

+10

تحصل على كلمتين، word1 وword2. يغيّر تعديل واحد word1 بإحدى ثلاث طرق: إدراج حرف في أي موضع، أو حذف حرف، أو استبدال حرف بحرف مختلف. أعد أقل عدد من التعديلات اللازمة لتحويل word1 إلى word2.

الدالة

minDistance(word1: string, word2: string) → integer

word1string: الكلمة التي تعدّلها
word2string: كلمة «يصل»
تُرجعinteger: أقل عدد من عمليات الإدراج والحذف والاستبدال التي تحوّل word1 إلى word2

القيود

1 ≤ word1.length ≤ 500
1 ≤ word2.length ≤ 500
تحتوي كلتا الكلمتين على أحرف إنجليزية صغيرة فقط.

أمثلة

المدخلات: word1 = "spot"word2 = "stop"
المخرجات: 2
الشرح: استبدل p بـ t وt بـ p: تصبح spot stot، ثم stop. تعديل واحد لا يكفي، لأن الكلمتين تختلفان في موضعين، كما أن الإدراج أو الحذف سيغيّر الطول.

المدخلات: word1 = "garden"word2 = "ardent"
المخرجات: 2
الشرح: احذف الحرف g لتحصل على arden، ثم أدرج t في النهاية لتحصل على ardent. سيكلّف استبدال الأحرف واحدًا تلو الآخر 6، لأن الكلمتين تختلفان في كل موضع.

المدخلات: word1 = "rain"word2 = "shine"
المخرجات: 3
الشرح: استبدل r بـ s وa بـ h لتحصل على shin، ثم أدرج e. لا يمكن فعل ذلك بتعديلين: لا يظهر الحرفان r وa في shine، لذا يتطلب كل منهما تعديلًا لا يجعل الكلمة أطول، وما زال يتعين زيادة طول الكلمة بحرف واحد.

+21 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك أيضًا إرجاع أقصر قائمة بالتعديلات، وليس عددها فقط؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

تتفاعل التعديلات مع بعضها، لذلك لا يمكنك إصلاح الكلمات موضعًا بموضع: تختلف garden وardent في المواضع الستة كلها، ومع ذلك يكفي تعديلان بمجرد حذف g وانتقال كل شيء إلى اليسار. تكمن الفكرة التي تحل المسألة في النظر فقط إلى الحرف الأخير من كل كلمة. إما أن يتطابق الحرفان بالفعل، أو أن أحد ثلاثة تعديلات بالضبط يجعلهما متطابقين، ويترك كل خيار المسألة نفسها على بادئات أقصر. يحل جدول من الإجابات بحجم (n+1) × (m+1) كل زوج من البادئات مرة واحدة، ويكفي صفّان منه.

جرّب التعديلات الثلاثة كلها باستخدام الاستدعاء الذاتي

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

لتكن edits(i, j) أقل عدد من التعديلات اللازمة لتحويل اللاحقة word1[i:] إلى word2[j:]. انظر إلى الحرفين الأولين من اللاحقتين. إذا كانا متساويين، فأبقِهما وتقدّم بالمؤشرين معًا: فالحرف المتطابق لا يحتاج أبدًا إلى تعديل، وأي خطة تنفق تعديلًا عليه يمكن تغييرها إلى خطة تُبقيه من دون أن تصبح أطول.

إذا كانا مختلفين، فلا بد أن يتعامل أحد التعديلات مع word1[i] أو أن ينتج word2[j]، وهناك ثلاث طرق بالضبط. استبدل word1[i] بـ word2[j]، وتقدّم بالمؤشرين معًا: edits(i+1, j+1). احذف word1[i]، وتقدّم بـ i فقط: edits(i+1, j). أدرج word2[j] قبله، وتقدّم بـ j فقط: edits(i, j+1). الإجابة هي 1 زائد أقل تكلفة من الطرق الثلاث. عندما تنفد word1، أدرج بقية word2، وتكون التكلفة m - j؛ وعندما تنفد word2، احذف بقية word1، وتكون التكلفة n - i.

هذه الطريقة بطيئة لأن كل اختلاف يبدأ ثلاثة استدعاءات. لكلمتين مكوّنتين من 15 حرفًا لا يشتركان في أي حرف، يصل عدد الاستدعاءات إلى نحو 6.7 × 10^10، بينما تحتوي الاختبارات الكبيرة على 500 حرف لكل كلمة. ومع ذلك، لا يوجد سوى (n+1) × (m+1) زوجًا مختلفًا (i, j)، لذا فإن كل استدعاء تقريبًا يكرر استدعاءً سابقًا.

الخوارزمية

اكتب edits(i, j) لللاحقتين اللتين تبدأان عند 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. يشير الفهرس 0 إلى بادئة فارغة.

الانتقالات. قارن الحرفين الأخيرين من البادئتين، word1[i-1] وword2[j-1]. إذا كانا متساويين، فأبقِهما كما هما: dp[i][j] = dp[i-1][j-1]، أي الخلية الواقعة قطريًا إلى أعلى اليسار. وإذا لم يكونا متساويين، فأضف تعديلًا واحدًا واختر الأقل كلفة من الجيران الثلاثة. تعني الخلية القطرية dp[i-1][j-1] استبدال word1[i-1] بـ word2[j-1]. وتعني الخلية التي فوقها، dp[i-1][j]، حذف word1[i-1]. أما الخلية التي إلى اليسار، dp[i][j-1]، فتعني إدراج word2[j-1] في النهاية.

الصف والعمود الأساسيان. على عكس كثير من مسائل الجداول، لا تكون قيمهما أصفارًا. يتطلب تحويل i أحرف إلى بادئة فارغة حذف i أحرف، لذا dp[i][0] = i. ويتطلب إنشاء j أحرف من لا شيء إدراج j أحرف، لذا dp[0][j] = j. تقرأ كل خلية قيمة الخلية التي فوقها، والخلية التي إلى يسارها، والخلية القطرية؛ لذا فإن ملء الجدول صفًا بعد صف، من اليسار إلى اليمين، يضمن أن تكون هذه القيم جاهزة. الإجابة هي dp[n][m].

إليك الجدول الخاص بتحويل spot إلى stop، بأعمدة للبادئات "" وs وst وsto وstop. الصف "" هو [0, 1, 2, 3, 4]، والصف s هو [1, 0, 1, 2, 3]، والصف sp هو [2, 1, 1, 2, 2]، والصف spo هو [3, 2, 2, 1, 2]، والصف spot هو [4, 3, 2, 2, 2]. تأمل بعض الخلايا. يتطابق s مع s، لذا تُنسخ القيمة القطرية 0. أما sp مع st فلا يتطابقان: قيم الجيران هي 0 قطريًا و1 أعلاه و1 إلى اليسار، لذا تكون القيمة 1 + 0 = 1، أي استبدال واحد. يتطابق spo مع sto عند الحرف o، فتُنسخ القيمة 1. تقارن الخلية الأخيرة، spot مع stop، الحرف t بالحرف p: قيم الجيران هي 1 و2 و2، لذا تكون الإجابة 1 + 1 = 2.

يحتوي الجدول على (n+1) × (m+1) خلية، ويتطلب كل منها عملًا ثابتًا، أي نحو 2.5 × 10^5 خطوة لكلمتين طول كل منهما 500 حرف. تملأ الاستدعاءات العودية المخزنة مؤقتًا الخلايا نفسها، لكنها قد تتعمق حتى n + m استدعاءً، وهو ما يتجاوز الحد الافتراضي في Python البالغ 1000.

الخوارزمية

أنشئ جدولًا dp يتكوّن من (n+1) × (m+1) خلية.
عيّن dp[i][0] = i لكل i وdp[0][j] = 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. يبدأ الصف 0 بالقيم [0, 1, 2, ..., m]، وهو الصف الأساسي.

يتطلب تحويل word2 إلى word1 العدد نفسه من التعديلات، لأن كل إدراج يتحول إلى حذف وكل حذف إلى إدراج. لذا يمكنك تبديل الكلمتين، وجعل الصفوف تمتد على طول الكلمة الأقصر. عندئذٍ يحتوي كل صف على min(n, m) + 1 عددًا بدلًا من جدول يصل حجمه إلى 251,001 خلية، وتظل كمية العمل O(n × m).

الخوارزمية

إذا كان word2 أطول من word1، فبدّلهما.
عيّن prev = [0, 1, ..., m]، حيث يمثّل 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، لذا يجب أن تكون dp[i][0] مساوية لـ i وأن تكون dp[0][j] مساوية لـ j.
نسيان cur[0] = i في النسخة ذات الصفين. يحتفظ المدخل الأول بقيمة من صفين سابقين، وتصبح كل خلية بعده خاطئة.
احتساب كلفة تعديل عند التطابق. جعل dp[i][j] = 1 + min(...) للأحرف المتساوية يعني أن تحويل a إلى a يكلف 1. عند التطابق، انسخ القيمة القطرية.
قراءة الجار الأيسر من prev بدلًا من cur. الجار الأيسر موجود في الصف الحالي: فهو عملية إدراج word2[j-1] بعد تحويل word1[:i] بالفعل إلى word2[:j-1].
المقارنة موضعًا بموضع. إن عدّ المواضع التي تختلف فيها الكلمتان يتجاهل عمليات الإدراج والحذف: يعطي 6 للكلمتين garden وardent، بينما الإجابة هي 2.
استخدام التخزين المؤقت مع الاستدعاء الذاتي للكلمات ذات 500 حرف. يصل عمق الاستدعاءات إلى 1000، وهو الحد الافتراضي في Python.

أسئلة شائعة4

ما هو التعقيد الزمني لمسافة التحرير؟

يعمل حل الجدول في زمن O(n × m)، حيث يمثّل n وm الطولين، لأنه يملأ خلية واحدة لكل زوج من البوادئ بعمل ثابت. ويستخدم ذاكرة O(n × m) للجدول الكامل، أو O(min(n, m)) باستخدام صفّين. أما الاستدعاء الذاتي البسيط دون جدول فزمنه أُسّي.

هل مسافة التحرير هي نفسها مسافة ليفنشتاين؟

نعم، هذه النسخة هي مسافة ليفنشتاين: تبلغ كلفة كلٍّ من الإدراج والحذف والاستبدال واحدًا. ومسافة التحرير هي الاسم العام لهذه الفئة. وتسمح الأنواع الأخرى بإجراء تعديلات أقل أو أكثر: فالإدراج والحذف فقط يعطيان n + m - 2 × LCS، والاستبدال فقط عند تساوي الأطوال يعطي مسافة هامنج، وإضافة تبديل حرفين متجاورين تعطي نسخة داميراو.

كيف تحصل على قائمة التعديلات، وليس على عددها فقط؟

احتفظ بالجدول كاملًا، ثم ارجع منه بدءًا من dp[n][m]. إذا تطابقت الحروف، فتحرّك قطريًا من دون إجراء أي تعديل. وإلا، فانتقل إلى الخانة المجاورة التي تقل قيمتها بمقدار واحد: الانتقال قطريًا يعني الاستبدال، والانتقال إلى الأعلى يعني الحذف، والانتقال إلى اليسار يعني الإدراج. توقّف عند dp[0][0]، واقرأ التعديلات بترتيب عكسي. لا يمكن لإصدار الصفّين إجراء ذلك بمفرده، لأنه تخلّص من الصفوف السابقة.

هل يمكن حل مسافة التحرير باستخدام مصفوفة واحدة؟

نعم. املأ مصفوفة واحدة row في مكانها، من اليسار إلى اليمين. قبل أن تستبدل row[j]، تظل تحتوي على القيمة من الصف السابق، بينما يحتوي row[j-1] بالفعل على قيمة الصف الحالي. القيمة الوحيدة التي تفقدها هي القيمة القطرية، لذا احتفظ بها في متغير: احفظ قيمة row[j] القديمة قبل الكتابة، واستخدمها كقيمة قطرية لـ j + 1.

Python

def minDistance(word1, word2):
    # اكتب الشيفرة هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

word1 = "spot"
word2 = "stop"

المتوقع

Edit Distance

الدالة

القيود

أمثلة

تلميحات

الحل

جرّب التعديلات الثلاثة كلها باستخدام الاستدعاء الذاتي

املأ جدول البوادئ

أبقِ على صفّين فقط

أخطاء شائعة وحالات حدّية

أسئلة شائعة4

مسائل مشابهة