Partition Labels

+10

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

الدالة

partitionLabels(s: string) → integer-array

sstring: السلسلة المراد اقتطاعها، أحرف صغيرة فقط
تُرجعinteger-array: طول كل جزء، من اليسار إلى اليمين

القيود

1 ≤ s.length ≤ 5 × 10⁴
s يحتوي على أحرف إنجليزية صغيرة فقط.
تحافظ الأجزاء على ترتيبها، وتشكل معًا كامل s، لذا فإن أطوالها تساوي s.length.

أمثلة

المدخلات: s = "abacdcefe"
المخرجات: [3, 3, 3]
الشرح: تقع حروف a عند الموضعين 0 و2، وحروف c عند الموضعين 3 و5، وحروف e عند الموضعين 6 و8، لذا تكون مواضع القطع بعد aba وبعد cdc. لا يمكن قطع أي جزء مرة أخرى، لأن كل جزء يبدأ وينتهي بالحرف نفسه.

تلميحات

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

فُتح 0 من 3

الحل

لا يُسمح بالقطع إلا في موضع لا يظهر فيه أي حرف على جانبيه، والإجابة الأفضل هي القطع عند كل موضع من هذا النوع. اختبار كل موضع بإعادة مسح السلسلة يستغرق زمنًا تربيعيًا. سجّل أولًا آخر موضع لكل حرف، ثم تعثر مرورٌ واحد من اليسار إلى اليمين على كل مواضع القطع، لأن الجزء يجب أن يمتد حتى آخر تكرار لكل حرف بداخله.

اختبر كل فجوة

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

الفكرة

توجد n-1 فجوات بين الحروف المتجاورة. لا يُسمح بالقطع في فجوة إلا إذا لم يظهر أي حرف على جانبيها، لأن الحرف الذي يُقسم بالقطع سيقع في جزأين. يمنحك إجراء كل القطوع المسموح بها أكبر عدد من الأجزاء. لنأخذ قطعة بين قطعين مسموح بهما متجاورين: لا يظهر أي حرف من حروفها إلى يسار القطع الأيسر أو إلى يمين القطع الأيمن، لذا تكون جميع نسخه داخل القطعة، فتكون جزءًا صالحًا. وأي إجابة صالحة لا يمكنها القطع إلا عند الفجوات المسموح بها، لذا لا توجد إجابة تتضمن أجزاءً أكثر.

إذًا، اختبر كل فجوة: اجمع الحروف الموجودة على يسارها وتلك الموجودة على يمينها، واقطع إذا لم يكن بين المجموعتين أي حرف مشترك. في abacdcefe، تحتوي الجهة اليسرى من الفجوة التي تأتي بعد aba على a وb، وتحتوي الجهة اليمنى على c وd وe وf. لا يوجد أي حرف مشترك، لذا تقطع. أما الفجوة التي تأتي بعد ab، فيوجد فيها الحرف a على الجانبين، لذا لا تقطع.

يقرأ كل اختبار السلسلة بأكملها، وهناك n-1 فجوات، لذا يبلغ عدد عمليات قراءة الحروف نحو n². مع وجود 50,000 حرف، يعني ذلك 2.5 × 10^9 عملية قراءة، وهذا أبطأ بكثير من أن يناسب أكبر الاختبارات.

الخوارزمية

عيّن start = 0، حيث يبدأ الجزء الحالي.
لكل فجوة cut من 1 إلى n-1 (الفجوة التي تسبق s[cut] مباشرةً)، ضع علامة على الأحرف في s[0..cut-1] والأحرف في s[cut..n-1].
إذا لم يكن هناك أي حرف يحمل علامة على كلا الجانبين، فأضف cut-start إلى الإجابة وعيّن start = cut.
بعد انتهاء الحلقة، أضف الجزء الأخير، n-start.

def partitionLabels(s):
    n = len(s)
    sizes = []
    start = 0  # where the current part begins
    for cut in range(1, n):  # the gap just before s[cut]
        left = set(s[:cut])
        right = set(s[cut:])
        if not (left & right):  # no letter on both sides: cut here
            sizes.append(cut - start)
            start = cut
    sizes.append(n - start)  # the last part has no gap after it
    return sizes

ادمج امتداد كل حرف

الفكرة

تخيّل كل حرف على أنه فترة تمتد من موضعه الأول إلى موضعه الأخير. يجب أن يغطي الجزء الذي يحتوي على حرف تلك الفترة كاملةً. لذلك، يجب أن يشترك حرفان تتداخل فترتاهما في جزء واحد، وينتشر التداخل: إذا تداخلت فترة a مع فترة b، وتداخلت فترة b مع فترة c، فستنتهي الأحرف الثلاثة في جزء واحد.

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

في codingisfun تكون الفترات بالترتيب كالتالي: c [0, 0]، و o [1, 1]، و d [2, 2]، و i [3, 6]، و n [4, 10]، و g [5, 5]، و s [7, 7]، و f [8, 8]، و u [9, 9]. تكون الأحرف الثلاثة الأولى منفردة. ابتداءً من i، تبدأ كل فترة عند الموضع 10 أو قبله، وهو موضع نهاية n، لذا تندمج في [3, 10]، وهو جزء يتكون من 8 أحرف.

تحتوي السلسلة على 26 حرفًا مختلفًا كحد أقصى، لذا يوجد 26 فترة كحد أقصى، كما أن جدولي المواضع الأولى والأخيرة لهما حجم ثابت.

الخوارزمية

في مرور واحد على s، سجّل first وlast، أي موضعَي الظهور الأول والأخير لكل حرف.
مرّ على s مرة أخرى. عندما يكون الموضع i هو موضع الظهور الأول لحرفه، يكون مجال ذلك الحرف [i, last] هو التالي حسب ترتيب البداية.
إذا بدأ المجال بعد end للكتلة الحالية، فأغلق الكتلة بطول end-start+1، وابدأ كتلة جديدة عند i.
في كلتا الحالتين، عيّن end = max(end, last).
أغلق الكتلة الأخيرة وأعِد الأطوال.

def partitionLabels(s):
    first, last = {}, {}
    for i, c in enumerate(s):
        first.setdefault(c, i)
        last[c] = i
    sizes = []
    start = end = 0  # the block of merged spans being built
    for i, c in enumerate(s):
        if first[c] != i:
            continue  # take each letter's span once, at its first position
        if i > end:  # this span starts after the block: close the block
            sizes.append(end - start + 1)
            start = i
        end = max(end, last[c])
    sizes.append(end - start + 1)
    return sizes

وسّع كل جزء حتى حرفه الأخير

الفكرة

المواضع الأولى ليست مطلوبة إطلاقًا. اقرأ السلسلة من اليسار إلى اليمين واحتفظ بـ end، وهو أبعد موضع أخير لأي حرف في الجزء الحالي. عندما تقرأ حرفًا عند i، يجب أن تكون آخر نسخة منه في هذا الجزء أيضًا، لذا مدّد end إلى last[s[i]] إذا كان ذلك أبعد.

عندما يصل i إلى end، تكون آخر نسخة من كل حرف قرأته في هذا الجزء عند i أو قبله. لا يعبر أي حرف الفجوة بعد i، لذا يُسمح بالفصل هناك. أنهِ الجزء، الذي طوله end-start+1، وابدأ الجزء التالي عند i+1.

لماذا يُعدّ الفصل عند أول فرصة هو الاختيار الجشع الصحيح؟ قبل أن يصل i إلى end، لا يزال لأحد أحرف الجزء نسخة أبعد إلى اليمين، لذا لا يُسمح بأي فصل أسبق. ولا تفوّت هذه العملية أي فجوة مسموح بها: إذا لم يعبر أي حرف الفجوة بعد i، تنتهي جميع أحرف الجزء عند i أو قبله، لذا يساوي end قيمة i عندها. تفصل العملية عند الفجوات المسموح بها بالضبط، وهذا يعطي أكبر عدد ممكن من الأجزاء.

في abacdcefe، المواضع الأخيرة هي a عند 2، وb عند 1، وc عند 5، وd عند 4، وe عند 8، وf عند 7. تؤدي قراءة a إلى ضبط end على 2، وتُبقيه b عند تلك القيمة، وعند i = 2 ينتهي الجزء بطول 3. ثم يضبط c قيمة end على 5 وينتهي الجزء عند 5، بطول 3 أيضًا. وينتهي جزء e عند 8.

الخوارزمية

في مرور واحد، خزّن last[c]، وهو موضع الظهور الأخير لكل حرف c، في مصفوفة من 26 عنصرًا.
عيّن start = 0 وend = 0.
لكل موضع i، عيّن end = max(end, last[s[i]]).
إذا كان i == end، فأضف end-start+1 إلى الإجابة وعيّن start = i+1.
أعِد الأطوال.

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}  # last position of each letter
    sizes = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])  # the part must reach c's last copy
        if i == end:  # no letter of this part appears later
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

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

التمرير الجشع قصير، لذا تكمن الأخطاء في الموضع الذي تُجري المقارنة معه وفي أطوال الأجزاء.

التقسيم عند الوصول إلى آخر ظهور للحرف الحالي بدلًا من end الخاص بالجزء. في abcba، يكون الحرف c عند الفهرس 2 آخر ظهور له، لكن ظهورات a تمتد حتى الفهرس 4، لذا فإن التقسيم عند ذلك الموضع سيجزّئ كلاً من a وb.
خطأ بمقدار واحد في الطول. الجزء الممتد من start إلى end، مع تضمين كليهما، يتكوّن من end-start+1 حرفًا.
إرجاع مواضع التقسيم بدلًا من الأطوال. بالنسبة إلى abacdcefe، الإجابة هي [3, 3, 3]، وليست [2, 5, 8].
نسيان الجزء الأخير عند التقسيم عند الفجوات. لا توجد فجوة بعد الجزء الأخير، لذا أضف n-start بعد انتهاء الحلقة.
توقّع جزء واحد لكل حرف مميّز. يحتوي zebraz على خمسة أحرف مختلفة، لكنه يشكّل جزءًا واحدًا، لأن حرفي z يضمان كل ما بينهما معًا.

أسئلة شائعة3

ما هو التعقيد الزمني لمسألة تقسيم التسميات؟

تمريرة واحدة تسجّل الموضع الأخير لكل حرف، وتمريرة ثانية تحدد مواضع القطع، لذا فالزمن هو O(n). يحتوي جدول المواضع الأخيرة على 26 مدخلًا أيًا كان طول السلسلة، لذا فالمساحة الإضافية هي O(1)، دون احتساب الناتج.

لماذا تنجح الطريقة الجشعة في تقسيم السلاسل إلى أقسام؟

يجب أن يصل الجزء الحالي إلى آخر نسخة من كل حرف يحتويه، لذا لا يُسمح بأي تقسيم قبل end. عند end لا يظهر أي حرف من الجزء لاحقًا، لذا يُسمح بالتقسيم، كما أن إجراؤه لا يضر ببقية السلسلة النصية. لذلك، يُجري المرور تقسيمًا عند كل موضع مسموح به، ولا يُجري أي تقسيم سواه، وهذا يحقق أكبر عدد ممكن من الأجزاء.

هل تُعدّ مسألة تقسيم التسميات مسألة دمج الفواصل الزمنية؟

نعم، لكن بصورة غير مباشرة. يغطي كل حرف الفترة من أول ظهور له إلى آخر ظهور، ويجب أن تتداخل الفترات في جزء مشترك، ودمجها يعطي الأجزاء نفسها تمامًا. التمريرة الجشعة هي عملية الدمج نفسها، لكن أثناء المرور: end هو الحد الأيمن للكتلة المدمجة حتى الآن.

def partitionLabels(s):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

s = "abacdcefe"

الإخراج المتوقع

[3, 3, 3]

Partition Labels

الدالة

القيود

أمثلة

تلميحات

الحل

اختبر كل فجوة

ادمج امتداد كل حرف

وسّع كل جزء حتى حرفه الأخير

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

أسئلة شائعة3

مسائل مشابهة