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: האם חלוקת פלינדרום היא תכנות דינמי או חיפוש לאחור?

היא משתמשת בשניהם. כדי למנות את כל החלוקות, עד 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] הוא פלינדרום, או אם יש בחלק לכל היותר 2 אותיות.

ניסיון של 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] לפני חישובו; מלאו את i מ-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 אותיות. במחרוזת שאין בה אותיות חוזרות יש בדיוק חלוקה אחת, כל אות בפני עצמה.

האם חלוקת פלינדרום היא תכנות דינמי או חיפוש לאחור?

היא משתמשת בשניהם. כדי למנות את כל החלוקות, עד 2^(n-1), נדרש חיפוש שבונה כל חלוקה חלק אחר חלק: חיפוש עם חזרה לאחור. תכנות דינמי מספק את טבלת הכן או לא של תתי־מחרוזות פלינדרומיות שהחיפוש קורא, והיא מתמלאת פעם אחת ב־O(n²).

def partition(s):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

ארגומנט

s = "aab"

הפלט הצפוי

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