Word Break

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

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

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

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

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

+10

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

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

פונקציה

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

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

אילוצים

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 בודדת, לכן אף חיתוך לא עובד.

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

התחייבות למילה אחת בכל פעם נכשלת, וניסיון של כל חיתוך הוא אקספוננציאלי. אבל האפשרות לחתוך את שאר s תלויה רק במקום שבו הוא מתחיל, ולכן יש רק n + 1 שאלות. להלן, n הוא האורך של s, m הוא מספר המילים ו-L הוא אורך המילה הארוכה ביותר.

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

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

האינטואיציה

החלק הראשון חייב להיות מילה שמתחילה ב־s. נסה כל מילה כזאת ושאל את אותה שאלה על האותיות שנותרו; שארית ריקה פירושה שכל האותיות חולקו. מעבר על כל מילה ראשונה, ואז על כל מילה שנייה, לא יכול לפספס חלוקה תקינה.

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

אלגוריתם

כתבו canSplit(start): האם אפשר לחתוך את האותיות מ־start ועד הסוף? אם start שווה לאורך של s, החזירו true.
עבור כל מילה ש־s מכיל באינדקס start, אם canSplit(start + its length) הוא 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. שומרים את התשובה עבור כל start פעם אחת ומשתמשים בה שוב.

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

כל start מנסה כל מילה, ומשווה עד L אותיות: זמן O(n × m × L), לכל היותר 6 × 10^6 בדיקות אותיות, ו־O(n) מקום.

אלגוריתם

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

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] שנחוץ לכם כבר ידוע.

הכניסו את המילים לקבוצת גיבוב. אף מילה אינה ארוכה מ־L, ולכן רק L החלקים שמסתיימים ב־end יכולים להתאים, בלי קשר לגודל המילון. עבור sunflowerseed, הערך canEnd הוא true במיקומים 0, 3, 7, 9 ו־13; המבוי הסתום במיקום 7 אינו מזיק.

בכל אחד מ־n המיקומים נבדקים לכל היותר L חלקים, וכל אחד מהם דורש עד L צעדים לבנייה ולחישוב הגיבוב: O(n × L²), לכל היותר 1.2 × 10^5 צעדים, ובנוסף O(m × L) עבור הקבוצה.

אלגוריתם

שים את המילים בקבוצת גיבוב; שים לב לאורך המרבי 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.
שמירת תשובות true בלבד בממנון. העבודה החוזרת מתרחשת בענפים של false, ולכן הדוגמה עם ה־a נשארת אקספוננציאלית.
יצירת טבלה עם ערך אחד פחות מהנדרש. canEnd זקוק ל־n + 1 ערכים, עבור אורכי קידומת מ־0 עד n.
השוואה מעבר לסוף של s, למשל השוואת המילה abc לשארית ab. בדקו קודם את האורכים.
ב־Lua וב־R, מיקומי המחרוזת מתחילים ב־1: חלק באורך k שמסתיים באות e מתחיל ב־e-k+1.

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

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

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

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

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

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

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

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

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

הפלט הצפוי

true

Word Break

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

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

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

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

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

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

בעיות דומות