Coding Interview Prep · درس

تقسيم السلسلة إلى مقاطع متناظرة II

اجمع بين جدول متناظرات محسوب مسبقًا وبرمجة ديناميكية أحادية البعد للعثور على الحد الأدنى من القطوع اللازمة لتقسيم سلسلة إلى مقاطع متناظرة.

تقسيم السلسلة إلى مقاطع متناظرة II درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.

المسألة: الحد الأدنى من عمليات القطع للتقسيم

تطلب مسألة Palindrome Partitioning II ما يلي: إذا أُعطيت السلسلة s، فاعثروا على الحد الأدنى من عمليات القطع بحيث تكون كل سلسلة فرعية في التقسيم متناظرة. بالنسبة إلى 'aab'، تكفي عملية قطع واحدة للحصول على ['aa', 'b']، لذا تكون الإجابة 1. أما بالنسبة إلى 'a' فالإجابة هي 0، لأنها متناظرة أصلًا. تجمع هذه المسألة بين مرحلتين من البرمجة الديناميكية: نحسب أولًا مسبقًا أي السلاسل الفرعية متناظرة، ثم نستخدم البرمجة الديناميكية أحادية البعد لإيجاد الحد الأدنى من عمليات القطع.

المرحلة 1: الحساب المسبق لجدول السلاسل المتناظرة

ابنوا أولًا is_pal[i][j] = True إذا كانت s[i..j] سلسلة متناظرة، وذلك باستخدام البرمجة الديناميكية على الفواصل. يستغرق هذا O(n²) من الزمن وO(n²) من المساحة. وبديلًا عن ذلك، يمكن للتوسّع حول المركز ملء الجدول نفسه بزمن O(n²). نحتاج إلى هذا الجدول لأن البرمجة الديناميكية للقطع أحادية البعد ستستعلم عن is_pal[i][j] مرارًا؛ والحساب المسبق يتجنب إعادة فحص التناظر داخل حلقة البرمجة الديناميكية للقطع.

def build_palindrome_table(s):
    n = len(s)
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for i in range(n-1):
        is_pal[i][i+1] = (s[i] == s[i+1])
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
    return is_pal

print(build_palindrome_table('aab'))

المرحلة 2: إعداد البرمجة الديناميكية للقطع أحادية البعد

عرّفوا cuts[i] على أنه الحد الأدنى من عمليات القطع اللازمة لتقسيم s[0..i]. إذا كانت s[0..i] نفسها متناظرة، فإن cuts[i] = 0. وإلا، فجرّبوا كل موضع تقسيم: لكل j من 0 إلى i-1، إذا كانت s[j+1..i] متناظرة، فإن cuts[i] = min(cuts[i], cuts[j] + 1). والسؤال هنا هو: ماذا لو كان الجزء الأخير من التقسيم هو s[j+1..i]؟ عندها نحتاج إلى cuts[j] من عمليات القطع للبادئة، إضافةً إلى عملية قطع واحدة.

def min_cut(s):
    n = len(s)
    is_pal = build_palindrome_table(s)
    cuts = [float('inf')] * n
    
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0  # entire prefix is a palindrome
        else:
            for j in range(i):
                if is_pal[j+1][i]:
                    cuts[i] = min(cuts[i], cuts[j] + 1)
    
    return cuts[n-1]

الحل الكامل والتتبّع

لنتتبّع التنفيذ على 'aab'. جدول السلاسل المتناظرة: is_pal[0][0]='a'=T، وis_pal[1][1]='a'=T، وis_pal[2][2]='b'=T، وis_pal[0][1]='aa'=T، وis_pal[1][2]='ab'=F، وis_pal[0][2]='aab'=F. عمليات القطع: cuts[0]=0 (‏'a' متناظرة)، وcuts[1]=0 (‏'aa' متناظرة)، أما cuts[2] فالسلسلة 'aab' غير متناظرة، لذا نجرّب j=1: ‏is_pal[2][2]=T، ومن ثم cuts[2] = cuts[1]+1 = 1. الإجابة: 1.

def build_palindrome_table(s):
    n = len(s)
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for i in range(n-1):
        is_pal[i][i+1] = (s[i] == s[i+1])
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
    return is_pal

def min_cut(s):
    n = len(s)
    is_pal = build_palindrome_table(s)
    cuts = [float('inf')] * n
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0
        else:
            for j in range(i):
                if is_pal[j+1][i]:
                    cuts[i] = min(cuts[i], cuts[j] + 1)
    return cuts[n-1]

print(min_cut('aab'))   # 1
print(min_cut('ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab'))

التعقيد الزمني وتعقيد المساحة

تستغرق المرحلة 1 (جدول السلاسل المتناظرة) O(n²) من الزمن وO(n²) من المساحة. أما المرحلة 2 (البرمجة الديناميكية للقطع)، فتحتوي على حلقة خارجية تمر على n مواضع وحلقة داخلية تمر على n مواضع للتقسيم، ولذلك تستغرق أيضًا O(n²) من الزمن. إجمالًا: O(n²) من الزمن وO(n²) من المساحة. يمكن تقليل المساحة إلى O(n) لمصفوفة القطع، لكن جدول السلاسل المتناظرة لا يزال يتطلب O(n²). يتوقع المُحاوِرون O(n²)؛ أما الحل بزمن O(n) باستخدام Manacher's فيتجاوز النطاق المعتاد.

التوسّع حول المركز لجدول السلاسل المتناظرة

بدلًا من أسلوب البرمجة الديناميكية على الفواصل لبناء جدول السلاسل المتناظرة، يمكنكم ملء is_pal باستخدام التوسّع حول المركز. لكل موضع مركزي، توسّعوا إلى الخارج وسجّلوا جميع السلاسل المتناظرة التي تعثرون عليها. يظل التعقيد O(n²) من الزمن وO(n²) من المساحة، لكنه قد يكون أسرع عمليًا بفضل الاستفادة الأفضل من ذاكرة التخزين المؤقت. كلا الأسلوبين مقبول في المقابلات.

def build_pal_expand(s):
    n = len(s)
    is_pal = [[False]*n for _ in range(n)]
    
    def expand(l, r):
        while l >= 0 and r < n and s[l] == s[r]:
            is_pal[l][r] = True
            l -= 1; r += 1
    
    for i in range(n):
        expand(i, i)    # odd-length centres
        expand(i, i+1)  # even-length centres
    return is_pal

print('Expand-around-centre palindrome table built')

تعداد جميع التقسيمات (الجزء الأول)

تطلب مسألة Palindrome Partitioning I (وهي مسألة ذات صلة) تعداد ALL للتقسيمات الصحيحة التي تكون فيها كل سلسلة فرعية متناظرة. تستخدم هذه المسألة التراجع مع جدول السلاسل المتناظرة المحسوب مسبقًا بوصفه أداةً للاستبعاد. وعلى خلاف البرمجة الديناميكية للحد الأدنى من القطوع التي تحسب عددًا، تعدّد هذه المسألة عددًا أُسّيًا من الحلول، ولذلك تُحلّ بأسلوب مختلف تمامًا.

def partition_all(s):
    n = len(s)
    is_pal = build_pal_expand(s)
    result = []
    
    def backtrack(start, path):
        if start == n:
            result.append(path[:])
            return
        for end in range(start, n):
            if is_pal[start][end]:
                path.append(s[start:end+1])
                backtrack(end+1, path)
                path.pop()
    
    backtrack(0, [])
    return result

print(partition_all('aab'))  # [['a','a','b'], ['aa','b']]

تهيئة cuts باستخدام n-1

إحدى الحيل الشائعة هي تهيئة cuts[i] = i بدلًا من inf، لأن أسوأ حالة لـ s[0..i] هي قطع كل محرف على حدة، ما يعطي i من عمليات القطع. وبذلك تتجنبون التحقق من inf في الشيفرة. عندما تكون is_pal[0][i] صحيحة، نستبدل القيمة بـ 0. توضّح هذه التهيئة الحد الأعلى لعدد عمليات القطع وتبسّط الشيفرة قليلًا.

def min_cut_clean(s):
    n = len(s)
    is_pal = build_palindrome_table(s)
    cuts = list(range(n))  # cuts[i] = i (worst case)
    
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0
        else:
            for j in range(1, i+1):
                if is_pal[j][i]:
                    cuts[i] = min(cuts[i], cuts[j-1] + 1)
    return cuts[n-1]

بديل: برمجة ديناميكية بمرور واحد دون جدول منفصل

يملأ أحد الأساليب الأنيقة جدول السلاسل المتناظرة وبرمجة القطع الديناميكية في الوقت نفسه. فعندما نوسّع السلاسل المتناظرة انطلاقًا من كل مركز، نحدّث مصفوفة cuts فورًا. بالنسبة إلى سلسلة متناظرة s[l..r]، يمكننا تحديث cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)). يتجنب هذا المرور المنفصل على جدول بحجم O(n²)، وقد يكون أوضح عند التنفيذ في مقابلة وتحت ضغط الوقت.

الحالات الحدّية التي ينبغي مراعاتها

من أهم الحالات الحدّية في مسألة تقسيم السلاسل المتناظرة II: (1) تعيد السلسلة ذات المحرف الواحد 0 من عمليات القطع؛ (2) تعيد السلسلة المتناظرة أصلًا 0 من عمليات القطع؛ (3) تحتاج السلسلة التي جميع محارفها مختلفة إلى n-1 من عمليات القطع؛ (4) تحتاج السلسلة التي جميع محارفها متطابقة (مثل 'aaaa') إلى 0 من عمليات القطع، لأن السلسلة بأكملها متناظرة. احرصوا دائمًا على التحقق من أن الحل يتعامل بصورة صحيحة مع الخروج المبكر عند is_pal[0][i] = True.

def build_palindrome_table(s):
    n = len(s)
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for i in range(n-1):
        is_pal[i][i+1] = (s[i] == s[i+1])
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
    return is_pal

def min_cut(s):
    n = len(s)
    is_pal = build_palindrome_table(s)
    cuts = list(range(n))
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0
        else:
            for j in range(1, i+1):
                if is_pal[j][i]:
                    cuts[i] = min(cuts[i], cuts[j-1] + 1)
    return cuts[n-1]

print(min_cut('a'))     # 0
print(min_cut('aaaa'))  # 0
print(min_cut('abc'))   # 2

نصائح للتواصل في المقابلة

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

تحقق سريع

اختبروا مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep التي تناولها هذا الدرس.

مراجعة الدرس

تعلمتم في هذا الدرس أن: تقسيم السلاسل المتناظرة II يستخدم مرحلتين من البرمجة الديناميكية — الحساب المسبق لجدول السلاسل المتناظرة ثم تشغيل البرمجة الديناميكية للقطع أحادية البعد، وأن العلاقة التكرارية للقطع هي cuts[i] = min(cuts[j-1] + 1) لكل j تحقق أن s[j..i] سلسلة متناظرة، وأن التعقيد الإجمالي هو O(n²) من الزمن وO(n²) من المساحة. سنتناول بعد ذلك مسألة Burst Balloons، التي تستخدم أسلوبًا ذكيًا من البرمجة الديناميكية العكسية على الفواصل.

الأسئلة الشائعة

هل درس «تقسيم السلسلة إلى مقاطع متناظرة II» مجاني؟

نعم — نص درس «تقسيم السلسلة إلى مقاطع متناظرة II» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.

ماذا ستتعلم في «تقسيم السلسلة إلى مقاطع متناظرة II»؟

اجمع بين جدول متناظرات محسوب مسبقًا وبرمجة ديناميكية أحادية البعد للعثور على الحد الأدنى من القطوع اللازمة لتقسيم سلسلة إلى مقاطع متناظرة. تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.

هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟

لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.

كم من الوقت يستغرق درس «تقسيم السلسلة إلى مقاطع متناظرة II»؟

معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.

هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟

نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.

جميع الدروس في هذه الدورة

نمط البرمجة الديناميكية للفواصل وترتيب الملء
أطول تتابع جزئي وسلسلة فرعية متناظرة
تقسيم السلسلة إلى مقاطع متناظرة II
تفجير البالونات: البرمجة الديناميكية العكسية للفواصل

← العودة إلى Coding Interview Prep