Word Break

Q: מהי סיבוכיות הזמן של Word Break?

טבלת bottom-up עם קבוצת גיבוב פועלת בזמן O(m × L + n × L²) , כאשר n הוא האורך של s , m הוא מספר המילים ו- L היא המילה הארוכה ביותר. בניית הקבוצה קוראת כל מילה פעם אחת, וכל אחד מ- n המיקומים מחפש לכל היותר L קטעים שאורכם עד L אותיות. אם במקום זאת משווים כל מילה בכל מיקום, הסיבוכיות היא O(n × m × L) . רקורסיה רגילה ללא זיכרון מטמון היא אקספוננציאלית.

Q: האם Word Break היא בעיית תכנות דינמי או בעיית גרפים?

שתי נקודות המבט עובדות. בתור תכנות דינמי, canEnd[i] עונה על השאלה אם אפשר לחתוך את i האותיות הראשונות, והוא נבנה מקידומות קצרות יותר. בתור גרף, כל אינדקס הוא צומת, ויש קשת מ־ i ל־ j כאשר האותיות מ־ i עד j יוצרות מילה, והשאלה היא אם צומת n נגיש מצומת 0. חיפוש לרוחב עם קבוצת ביקור עושה את אותה העבודה כמו הטבלה.

בינוניתכנון דינמי גיבוב

+10

נתונה לך מחרוזת s ורשימת מילים wordDict. החזר true אם אפשר לחתוך את s לחלקים כך שכל חלק יהיה מילה מתוך wordDict, ואחרת החזר false.

החלקים שומרים על הסדר שלהם, וביחד משתמשים בכל אות של s בדיוק פעם אחת. אפשר להשתמש במילה כל מספר פעמים, ואין צורך להשתמש בכל המילים.

פונקציה

wordBreak(s: string, wordDict: string-array) → boolean

sstring: המחרוזת שיש לחלק למילים
wordDictstring-array: המילים שבהן מותר לך להשתמש, כל אחת כמה פעמים שתרצה
מחזירהboolean: אמת אם ניתן לפצל את s למילים מהמילון, אחרת שקר

אילוצים

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s וגם כל מילה מורכבת מאותיות אנגליות קטנות בלבד.
המילים בתוך wordDict שונות זו מזו.

דוגמאות

קלט: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
פלט: true
הסבר: חלקו אותה ל־sun, flower, seed. בחירה ב־flow אחרי sun לא תוביל לשום מקום, מכיוון שאין מילה שמתחילה ב־er שנותר, ולכן המילה הראשונה שמתאימה אינה תמיד המילה הנכונה.

קלט: s = "bananaban"wordDict = ["ban", "ana"]
פלט: true
הסבר: ban + ana + ban מכסה את המחרוזת ומשתמש ב-ban פעמיים, וזה מותר.

קלט: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
פלט: false
הסבר: המחרוזת מתחילה ב־pine + apple או ב־pineapple, ובשני המקרים נשאר tart. המילה היחידה שמתאימה שם היא tar, שמשאירה t בודדת, ולכן אף חיתוך לא עובד.

+21 בדיקות נסתרות בשליחה

שאלת המשך

החזר את מספר המילים הקטן ביותר שחתך תקף יכול להשתמש בהן, או -1 אם אי אפשר לחתוך את s. מה משתנה בטבלה, והאם זמן הריצה משתנה?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

חיתוך חמדני נכשל בשני הכיוונים: בחירת המילה הקצרה ביותר תחילה מפרקת את sunflowerseed ל־sun + flow, ובחירת המילה הארוכה ביותר תחילה חותכת את carpetal ל־carpet ומשאירה את al ללא פתרון. לכן צריך לנסות את האפשרויות, ואפשר לחתוך מחרוזת במספר דרכים שגדל באופן מעריכי. המפתח הוא שהיכולת לחתוך את שאר המחרוזת תלויה רק במיקום שממנו השאר מתחיל, ולכן יש רק n + 1 שאלות שונות. להלן, n הוא האורך של s, m הוא מספר המילים ו־L הוא אורך המילה הארוכה ביותר.

נסו כל מילה בכל מיקום

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

קרא את s משמאל. לא משנה מה תהיה החתיכה הראשונה, היא חייבת להיות מילה ש-s מתחילה בה. נסה כל מילה כזאת, ולגבי כל אחת מהן שאל את אותה שאלה על האותיות שנותרו. אם מילה כלשהי מובילה לחיתוך מלא, התשובה היא true. אם אף אחת מהן לא מובילה לכך, התשובה היא false. כשלא נשאר דבר, חיתכת את כל האותיות, ולכן זה נחשב להצלחה.

הפעולה הזאת מנסה כל מילה ראשונה אפשרית, אחר כך כל מילה שנייה אפשרית, וכן הלאה, ולכן היא לא יכולה לפספס חיתוך תקף, וכל true שהיא מחזירה מלווה בחיתוך אמיתי.

הפעולה איטית כי היא בודקת שוב ושוב את אותן שאריות. קח 299 עותקים של a ואחריהם b אחד, כאשר המילים הן a, aa וכן הלאה, עד עשר אותיות a. כל דרך לחלק את אותיות ה-a לבלוקים שאורכם לכל היותר עשר מגיעה אל b ונכשלת שם, ויש יותר מ-10^89 דרכים כאלה. הרקורסיה חייבת לנסות את כולן לפני שהיא יכולה להחזיר תשובה false.

אלגוריתם

כתבו פונקציית עזר canSplit(start) שקובעת אם אפשר לחלק את האותיות מהאינדקס start ועד הסוף למילים.
אם start שווה לאורך של s, החזירו true.
עבור כל מילה, בדקו אם היא מופיעה ב-s החל מהאינדקס start.
אם כן, וגם canSplit(start + length of the word) הוא true, החזירו true.
אם אף מילה אינה מתאימה, החזירו false. התשובה היא canSplit(0).

def wordBreak(s, wordDict):
    def can_split(start):
        # Can s[start:] be cut into dictionary words?
        if start == len(s):
            return True  # nothing left to cut
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                return True
        return False

    return can_split(0)

רקורסיה עם זיכרון מטמון

האינטואיציה

התשובה עבור שארית תלויה רק במקום שבו היא מתחילה, ול־start יש רק n + 1 ערכים אפשריים. בדוגמה של האותיות a, מגיעים לשארית שמתחילה באינדקס 20 אחרי שני בלוקים של עשר, אחרי עשרים מופעים בודדים של a ובדרכים רבות מאוד אחרות, והתשובה שלה היא false בכל פעם. שמרו את התשובה עבור כל נקודת התחלה בפעם הראשונה שאתם מחשבים אותה, וקראו אותה שוב לאחר מכן.

לכל תא בזיכרון המטמון דרושים שלושה מצבים: עדיין לא חושב, true ו־false. התשובות false הן החשובות. תשובת true מסיימת מיד את כל החיפוש, ולכן העבודה שהרקורסיה הפשוטה חוזרת עליה מתבצעת כולה בענפים שנכשלים.

כל נקודת התחלה מחושבת פעם אחת ומנסה כל מילה, תוך השוואה של עד L אותיות, ולכן זמן הריצה הוא O(n × m × L): כאן יש לכל היותר 300 × 1000 × 20 = 6 × 10^6 בדיקות אותיות. זיכרון המטמון ומחסנית הקריאות צורכים O(n) מקום, והקריאות מקוננות לעומק של עד 300.

אלגוריתם

צרו טבלת זיכרון עם משבצת אחת לכל אינדקס, וסמנו כל אחת מהן ככזו שטרם חושבה.
ב־canSplit(start), החזירו true בסוף המחרוזת, והחזירו את התשובה השמורה אם יש תשובה במשבצת של start.
אחרת נסו כל מילה שמתחילה ב־start, כמו ברקורסיה הפשוטה, ועצרו בראשונה שאפשר לפצל את יתרת המחרוזת שלה.
שמרו את התוצאה במשבצת, כולל false, והחזירו אותה.
החזירו את canSplit(0).

def wordBreak(s, wordDict):
    memo = [None] * len(s)  # memo[start]: answer for s[start:], None until worked out

    def can_split(start):
        if start == len(s):
            return True
        if memo[start] is not None:
            return memo[start]
        result = False
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                result = True
                break
        memo[start] = result
        return result

    return can_split(0)

מלמטה למעלה, על פני תחיליות, באמצעות קבוצת גיבוב

האינטואיציה

הפכו את הכיוון ועבדו עם תחיליות. נסמן ב־canEnd[i] האם אפשר לחלק את i האותיות הראשונות למילים. תחילית ריקה אינה זקוקה למילים, ולכן canEnd[0] הוא true. אפשר לחלק את end האותיות הראשונות בדיוק כאשר החלק האחרון שלהן, האותיות מ־start עד end, הוא מילה, ואפשר לחלק את האותיות שלפניו, כלומר canEnd[start] הוא true. מלאו את הטבלה משמאל לימין, וכל ערך של canEnd[start] שתצטרכו כבר יהיה ידוע.

במקום להשוות את כל m המילים בכל מיקום, הכניסו את המילים לקבוצת גיבוב וחפשו בה את החלקים האפשריים האחרונים. אף מילה אינה ארוכה מ־L, ולכן רק L החלקים שמסתיימים ב־end יכולים להתאים. עבור sunflowerseed, הערך של canEnd נעשה true במיקומים 0, 3 (sun), 7 (flow), 9 (flower) ו־13 (seed אחרי מיקום 9), ולכן התשובה היא true. ממיקום 7 אי אפשר להתקדם, כי שום מילה אינה מתחילה ב־er, והטבלה אינה מושפעת מכך.

יש n מיקומים, ובכל אחד מהם מחפשים לכל היותר L חלקים; בניית חלק וחישוב הגיבוב שלו דורשים עד L צעדים. כלומר, O(n × L²), ולכל היותר 300 × 20 × 20 = 1.2 × 10^5 צעדים של מעבר על אותיות, ללא קשר לגודל המילון. בניית הקבוצה קוראת כל מילה פעם אחת, O(m × L), ולכן הסיבוכיות הכוללת היא O(m × L + n × L²). הקבוצה מכילה את המילים, O(m × L) אותיות, והטבלה מכילה n + 1 דגלים. אין רקורסיה.

אלגוריתם

הכניסו כל מילה לקבוצת גיבוב, וציינו את האורך L של המילה הארוכה ביותר.
צרו את canEnd עם n + 1 איברים, כולם false, והגדירו את canEnd[0] ל-true.
עבור כל end מ-1 עד n, נסו כל length מ-1 עד min(L, end).
אם canEnd[end-length] הוא true והחלק באורך הזה שמסתיים ב-end נמצא בקבוצה, הגדירו את canEnd[end] ל-true והפסיקו לנסות אורכים.
החזירו את canEnd[n].

def wordBreak(s, wordDict):
    words = set(wordDict)
    longest = max(len(word) for word in wordDict)
    n = len(s)
    # can_end[i]: the first i letters split into dictionary words
    can_end = [False] * (n + 1)
    can_end[0] = True  # the empty prefix needs no words
    for end in range(1, n + 1):
        # The last word is s[end-length:end], and no word is longer than longest.
        for length in range(1, min(longest, end) + 1):
            if can_end[end - length] and s[end - length:end] in words:
                can_end[end] = True
                break
    return can_end[n]

מלכודות ומקרי קצה

רוב התשובות השגויות נובעות מהתחייבות לחלוקה אחת מוקדם מדי, או מחיפוש שאינו זוכר את הכישלונות שלו.

חלוקה באופן חמדני. בחירת המילה הארוכה ביותר תחלק את carpetal ל־carpet ותשאיר את al, אף על פי ש־car + petal עובד. בחירת המילה הקצרה ביותר תחילה נכשלת במקרה של sunflowerseed.
בדיקה רק שכל אות של s מופיעה באיזושהי מילה. עם המילים aaaa ו־aa, לכל חלק יש אורך זוגי, ולכן אי אפשר לחלק את aaaaaaa, שאורכה שבע אותיות.
שמירת התשובות true בלבד במטמון. תשובת true מסיימת את החיפוש בכל מקרה. העבודה החוזרת מתרחשת בענפי false, ולכן מטמון שלא כולל אותם משאיר את החיפוש אקספוננציאלי.
יצירת טבלה עם איבר אחד פחות מהנדרש. canEnd[i] מתייחס ל־i האותיות הראשונות, וגם 0 וגם n הם ערכים תקפים, ולכן נדרשים n + 1 איברים.
השוואה מעבר לסוף של s כשמילה ארוכה יותר מהחלק שנותר, למשל המילה abc מול ab. בדקו את האורכים לפני שאתם משווים אותיות.
ב־Lua וב־R, מיקומי המחרוזת מתחילים ב־1: חלק באורך k שמסתיים באות e מתחיל באות e-k+1.

שאלות נפוצות4

מהי סיבוכיות הזמן של Word Break?

טבלת bottom-up עם קבוצת גיבוב פועלת בזמן O(m × L + n × L²), כאשר n הוא האורך של s, m הוא מספר המילים ו-L היא המילה הארוכה ביותר. בניית הקבוצה קוראת כל מילה פעם אחת, וכל אחד מ-n המיקומים מחפש לכל היותר L קטעים שאורכם עד L אותיות. אם במקום זאת משווים כל מילה בכל מיקום, הסיבוכיות היא O(n × m × L). רקורסיה רגילה ללא זיכרון מטמון היא אקספוננציאלית.

למה גישה חמדנית נכשלת בבעיית Word Break?

כלל חמדני מתחייב למילה אחת ולעולם לא שוקל אותה מחדש. בחירה במילה הארוכה ביותר תחילה מחלקת את carpetal ל-carpet ול-al, בעוד ש-car + petal עובד. בחירה במילה הקצרה ביותר תחילה מחלקת את sunflowerseed ל-sun + flow ונתקעת ב-erseed. תכנות דינמי שומר כל מיקום שאליו אפשר להגיע באמצעות חלוקה כלשהי, ולכן לא מאבד את המיקום הנכון.

האם Word Break היא בעיית תכנות דינמי או בעיית גרפים?

שתי נקודות המבט עובדות. בתור תכנות דינמי, canEnd[i] עונה על השאלה אם אפשר לחתוך את i האותיות הראשונות, והוא נבנה מקידומות קצרות יותר. בתור גרף, כל אינדקס הוא צומת, ויש קשת מ־i ל־j כאשר האותיות מ־i עד j יוצרות מילה, והשאלה היא אם צומת n נגיש מצומת 0. חיפוש לרוחב עם קבוצת ביקור עושה את אותה העבודה כמו הטבלה.

איך מציגים את כל המשפטים במקום להחזיר true או false?

השתמשו בחיפוש עם חזרה לאחור: בכל אינדקס נסו כל מילה שמתאימה והמשיכו ברקורסיה על שארית המחרוזת, תוך כדי בניית המשפט. זכרו את רשימת המשפטים עבור כל אינדקס, כך שכל שארית תיפתר פעם אחת בלבד. הריצו תחילה את טבלת האמת או השקר, כדי שמחרוזת שאי אפשר לפלח תדלג על החיפוש. מספר המשפטים יכול לגדול באופן מעריכי, ולכן גודל הפלט קובע את זמן הריצה.

Python

def wordBreak(s, wordDict):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s = "sunflowerseed"
wordDict = ["sun", "flow", "flower", "seed"]

צפוי

true

Word Break

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

נסו כל מילה בכל מיקום

רקורסיה עם זיכרון מטמון

מלמטה למעלה, על פני תחיליות, באמצעות קבוצת גיבוב

מלכודות ומקרי קצה

שאלות נפוצות4

בעיות דומות