Palindrome Partitioning

Q: ما هو التعقيد الزمني لتقسيم السلسلة إلى أجزاء متناظرة؟

في سلسلة من الأحرف المتطابقة، تكون جميع التقسيمات 2^(n-1) إجابات، ويصل طول كل منها إلى 2n-1 حرفًا: O(n × 2^n) . لا توجد طريقة أفضل من ذلك، لأن كتابة الإجابة تكلّف المقدار نفسه. يضيف جدول المتناظرات O(n²) من الزمن والمساحة، ويضيف الاستدعاء الذاتي O(n) .

Q: كم عدد تقسيمات السلسلة النصية إلى مقاطع متناظرة يمكن أن تحتوي عليها؟

بحد أقصى 2^(n-1) ، تقسيم واحد لكل طريقة لاختيار أيٍّ من الفجوات n-1 التي سنقطع عندها. وتبلغ سلسلة من الأحرف المتطابقة هذا الحد: 1,024 تقسيمًا لـ 11 حرفًا. أما السلسلة التي لا تحتوي على أحرف مكررة، فلها تقسيم واحد بالضبط، حيث يكون كل حرف بمفرده.

Q: هل تُحلّ مسألة Palindrome Partitioning باستخدام البرمجة الديناميكية أم التراجع؟

يستخدم كليهما. يتطلب تعداد ما يصل إلى 2^(n-1) من عمليات التقسيم بحثًا يبني كل تقسيم قطعةً قطعةً: التراجع. توفّر البرمجة الديناميكية جدولًا للإجابة بنعم أو لا عن المقاطع الفرعية المتناظرة التي يقرأها البحث، ويُملأ مرة واحدة في O(n²) .

متوسطالتراجع البرمجة الديناميكية

+10

تُقرأ المتناظرة بالطريقة نفسها من اليسار إلى اليمين ومن اليمين إلى اليسار. قسّم السلسلة s إلى قطعة واحدة أو أكثر بحيث تكون كل قطعة متناظرة، وأعِد كل الطرق الممكنة لذلك.

اكتب كل تقسيم على هيئة قطعه بالترتيب، مع الفصل بينها باستخدام |: تقسيم aab إلى a وa وb يعطي a|a|b. أعِد التقسيمات مرتبة تصاعديًا حسب رموز الأحرف، بحيث يأتي | بعد كل حرف صغير.

الدالة

partition(s: string) → string-array

sstring: سلسلة الأحرف الصغيرة المراد تقسيمها
تُرجعstring-array: كل تقسيم للسلسلة s إلى سلاسل متناظرة، مع كتابة | بين الأجزاء، بترتيب تصاعدي

القيود

1 ≤ s.length ≤ 11
s يحتوي على أحرف إنجليزية صغيرة فقط.
سلسلة مكوّنة من 11 حرفًا متطابقًا لها 1,024 تقسيمًا، وهي أكبر إجابة.

أمثلة

المدخلات: s = "aab"
المخرجات: ["aa|b", "a|a|b"]
الشرح: فقط aa|b وa|a|b تتكوّنان بالكامل من مقاطع متناظرة؛ أما a|ab فيفشل بسبب ab. يأتي aa|b أولًا في الترتيب: عند الحرف الثاني لديه a، بينما لدى الآخر |، الذي يأتي بعد كل حرف في الترتيب.

المدخلات: s = "abba"
المخرجات: ["abba", "a|bb|a", "a|b|b|a"]
الشرح: abba هي نفسها متناظرة، لذا فإن السلسلة غير المقسمة تُعدّ تقسيمًا وتأتي أولًا: محرفها الثاني حرف. تأتي a|bb|a قبل a|b|b|a: ففي المحرف الرابع لديها b بينما لدى الأخرى |.

سؤال إضافي

هل يمكنك إيجاد أقل عدد من القطوع اللازمة لتقسيم s إلى متلازمات، للسلاسل التي يصل طولها إلى 2,000؟

تلميحات

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

فُتح 0 من 3

الحل

كل فجوة من الفجوات n-1 بين الحروف إما أن تُقطَع أو لا، لذا توجد 2^(n-1) طريقة للتقسيم، ويمكن أن تكون جميعها إجابات. لا يمكنك تقليل حجم المخرجات، لكن يمكنك تخطي التقسيمات غير الصالحة: أنشئ كل تقسيم من اليسار إلى اليمين، واقطع الأجزاء المتناظرة فقط، واقرأ المتناظرات من جدول يُملأ مرة واحدة.

جرّب كل مجموعة من القطوع

الفكرة

رقّم التقسيمات بالأعداد الصحيحة من 0 إلى 2^(n-1)-1، بحيث يحدد كل بت ما إذا كان قد تم القطع عند فجوة. احتفظ بتقسيم العدد إذا كان كل جزء فيه متناظرًا قراءته من الجهتين.

إذا كانت أعلى بت تمثل الفجوة الأولى، فإن العد تصاعديًا يسرد التقسيمات بترتيب تصاعدي. بالنسبة إلى عددين، فإن أعلى بت يختلفان عندها تمثل أسبق فجوة يقطع عندها أحدهما ولا يقطعها الآخر. قبلها تكون السلاسل متساوية؛ وعندها يحتوي العدد الأصغر على حرف، بينما يحتوي الأكبر على |، الذي يأتي ترتيبه بعد كل حرف. بالنسبة إلى aab، يعطي 1 القيمة aa|b، ويعطي 3 القيمة a|a|b.

عند 11 حرفًا، يعني ذلك 1,024 قناعًا، يحتوي كل منها على 11 حرفًا. الهدر ناتج عن التقسيمات المرفوضة: إذ ينشئ abcdefghijk جميع القيم الـ1,024 للعثور على إجابة واحدة.

الخوارزمية

كرّر قيمة mask من 0 إلى 2^(n-1)-1.
مرّ على الحروف؛ أنهِ جزءًا بعد الحرف i عندما يكون i هو الفهرس الأخير أو يكون البت n-2-i في mask مضبوطًا.
تحقّق من كل جزء باستخدام مؤشّرين يتحرّكان نحو الداخل.
إذا كان كل جزء متناظرًا، فصِل الأجزاء باستخدام | وأضف السلسلة إلى الإجابة.
أعِد الإجابة؛ فهي مرتّبة مسبقًا لأن الفجوة الأولى هي البت الأعلى.

def partition(s):
    n = len(s)
    result = []
    # Bit (n-2-i) of mask says whether to cut after s[i]. Counting the
    # masks up from 0 lists the splits in sorted order.
    for mask in range(1 << (n - 1)):
        pieces = []
        start = 0
        for i in range(n):
            if i == n - 1 or (mask >> (n - 2 - i)) & 1:
                pieces.append(s[start:i + 1])
                start = i + 1
        if all(piece == piece[::-1] for piece in pieces):
            result.append("|".join(pieces))
    return result

التراجع باستخدام جدول متناظرات الحروف

الفكرة

الجزء الأول هو بادئة متناظرة s[0..end]، وتقسيم الباقي هو المسألة نفسها بدءًا من end+1. لذا تجرّب backtrack(start) كل قيمة end يكون فيها s[start..end] متناظرًا، وتضيف الجزء، ثم تستدعي نفسها تكراريًا، وتزيله. ينتهي كل فرع بإجابة، لأن الحرف الواحد متناظر، لذا يتناسب العمل مع حجم المخرجات: بالنسبة إلى abcdefghijk، يسلك البحث مسارًا واحدًا.

تتكرر الحاجة إلى معرفة ما إذا كان s[start..end] متناظرًا في فروع كثيرة، لذا اقرأ ذلك من جدول: تكون s[i..j] كذلك عندما s[i] == s[j] ويكون الجزء الداخلي s[i+1..j-1] كذلك، أو عندما يتكون الجزء من حرفين على الأكثر.

تجربة end بدءًا من الفهرس الأخير تعطي مخرجات مرتبة. يتفق تقسيمان يختلفان في جزئهما الأول حتى نهاية الجزء الأقصر؛ عندها يحتوي الأقصر على | ويحتوي الأطول على حرف، لذا يأتي الجزء الأول الأطول أولًا في الترتيب.

الخوارزمية

املأ pal[i][j] من أجل i بدءًا من n-1 نزولًا إلى 0: s[i] == s[j] وإما j-i < 2 أو pal[i+1][j-1].
اكتب backtrack(start). إذا كان start يساوي n، فادمج الأجزاء الحالية باستخدام | واحفظ السلسلة.
وإلا، كرّر على end بدءًا من n-1 نزولًا إلى start، وتخطّاه ما لم يتحقق pal[start][end].
أضف s[start..end] إلى الأجزاء، واستدعِ backtrack(end+1)، ثم أزل الجزء.
استدعِ backtrack(0) وأعِد التقسيمات المحفوظة، المرتبة مسبقًا.

def partition(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways.
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
    result = []
    parts = []

    def backtrack(start):
        if start == n:
            result.append("|".join(parts))
            return
        # Longest piece first: "|" sorts after every letter, so a longer
        # first piece gives a smaller string and the output stays sorted.
        for end in range(n - 1, start - 1, -1):
            if pal[start][end]:
                parts.append(s[start:end + 1])
                backtrack(end + 1)
                parts.pop()

    backtrack(0)
    return result

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

تجربة الجزء الأقصر أولًا. التقسيمات صحيحة، لكن الترتيب خاطئ: a|a|b قبل aa|b.
الفرز في النهاية بمقارنة تتبع قواعد اللغة أو الإعدادات المحلية، ما قد يضع | قبل الحروف. قارن رموز المحارف، أو أنشئ التقسيمات بالترتيب.
ملء جدول التناظر مع زيادة i. عندئذٍ تتم قراءة pal[i+1][j-1] قبل حسابه؛ املأ الجدول بدءًا من n-1 نزولًا.
الخلط بين end الشامل ونهاية المقطع الفرعي الحصرية. يحتوي الجزء s[start..end] على end-start+1 حرفًا.
حفظ قائمة الأجزاء المشتركة بدلًا من السلسلة الموصولة. يستمر البحث في تغيير تلك القائمة، لذا ينتهي الأمر بأن تكون كل الإدخالات المحفوظة متطابقة.

أسئلة شائعة3

ما هو التعقيد الزمني لتقسيم السلسلة إلى أجزاء متناظرة؟

في سلسلة من الأحرف المتطابقة، تكون جميع التقسيمات 2^(n-1) إجابات، ويصل طول كل منها إلى 2n-1 حرفًا: O(n × 2^n). لا توجد طريقة أفضل من ذلك، لأن كتابة الإجابة تكلّف المقدار نفسه. يضيف جدول المتناظرات O(n²) من الزمن والمساحة، ويضيف الاستدعاء الذاتي O(n).

كم عدد تقسيمات السلسلة النصية إلى مقاطع متناظرة يمكن أن تحتوي عليها؟

بحد أقصى 2^(n-1)، تقسيم واحد لكل طريقة لاختيار أيٍّ من الفجوات n-1 التي سنقطع عندها. وتبلغ سلسلة من الأحرف المتطابقة هذا الحد: 1,024 تقسيمًا لـ 11 حرفًا. أما السلسلة التي لا تحتوي على أحرف مكررة، فلها تقسيم واحد بالضبط، حيث يكون كل حرف بمفرده.

هل تُحلّ مسألة Palindrome Partitioning باستخدام البرمجة الديناميكية أم التراجع؟

يستخدم كليهما. يتطلب تعداد ما يصل إلى 2^(n-1) من عمليات التقسيم بحثًا يبني كل تقسيم قطعةً قطعةً: التراجع. توفّر البرمجة الديناميكية جدولًا للإجابة بنعم أو لا عن المقاطع الفرعية المتناظرة التي يقرأها البحث، ويُملأ مرة واحدة في O(n²).

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

اختبار #1

اختبار #2

وسيط

s = "aab"

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

["aa|b", "a|a|b"]