Decode Ways

Q: איך מטפלים באפסים ב-Decode Ways?

המספר 0 לעולם לא יכול להיות אות בפני עצמו, ולכן הוא חייב להתחבר לספרה שלפניו, ורק 10 ו- 20 הם קודים. בלולאה מלמטה למעלה, המשמעות היא ש- 0 אינו מוסיף דבר במקרה של ספרה אחת, ומוסיף את הספירה מלפני שתי ספרות רק אחרי 1 או 2. 0 מוביל, שני אפסים ברצף, או 0 אחרי ספרה בין 3 ל-9 גורמים לתשובה להיות 0.

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

+10

הודעה באותיות גדולות הומרה לספרות באמצעות הקוד A = 1, B = 2 וכן הלאה עד Z = 26, והקודים נכתבו בזה אחר זה ללא מפרידים. נתונה לך מחרוזת הספרות s. החזר את מספר ההודעות השונות שיכלו ליצור אותה.

כל אות נקראת מספרה אחת או משתי ספרות סמוכות, וקוד לעולם אינו מתחיל ב־0: 06 אינו 6, ו־0 בפני עצמו אינו אות. אם שום קריאה אינה אפשרית, החזר 0.

פונקציה

numDecodings(s: string) → integer

sstring: מחרוזת הספרות לפענוח
מחזירהinteger: מספר הודעות האותיות שמקודדות ל־s

אילוצים

1 ≤ s.length ≤ 100
s מכילה רק את הספרות 0 עד 9, והיא עשויה להתחיל ב־0.
לכל תחילית ולכל סופית של s יש פחות מ־2³¹ קריאות, ולכן התשובה וכל ספירה שתבנו בדרך נכנסות למספר שלם חתום בן 32 סיביות.

דוגמאות

קלט: s = "2611"
פלט: 4
הסבר: ארבע הקריאות הן 2 6 1 1 (BFAA), 26 1 1 (ZAA), 2 6 11 (BFK) ו-26 11 (ZK). הספרות האמצעיות לעולם אינן מתחברות לזוג, כי 61 גדול מ-26.

קלט: s = "1203"
פלט: 1
הסבר: ה־0 חייב להיות משויך ל־2 שלפניו בתור 20, מה שכופה את הקריאה 1 20 3 (ATC). קריאה של 12 תחילה תשאיר את ה־0 לבדו, ו־03 מתחיל ב־0.

קלט: s = "06"
פלט: 0
הסבר: האות הראשונה תצטרך להתחיל ב־0. 0 לבדו אינו אות, ו־06 אינו קוד, ולכן אף הודעה לא נותנת את המחרוזת הזאת.

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

שאלת המשך

מה אם s יכול להכיל גם *, שמייצג כל ספרה מ־1 עד 9? האם תוכל לספור את הקריאות בזמן O(n), ולהחזיר את הספירה מודולו 10^9+7?

רמזים

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

נפתחו 0 מתוך 3

פתרון

כל ספרה היא אות בפני עצמה או מצטרפת לשכנה שלה ויוצרת אות בת שתי ספרות, ולכן מספר הפענוחים גדל כמו מספרי פיבונאצ'י: כבר ל־45 ספרות 1 יש 1836311903 פענוחים. אין טעם לנסות למנות את הפענוחים. מה שפותר את הבעיה הוא שמספר הדרכים להשלים פענוח תלוי רק במיקום שאליו הגעת, ולכן צריך לספור כל מיקום פעם אחת. צריך להיזהר עם האפסים: 0 יכול להיות רק הספרה השנייה של 10 או 20.

נסו את שתי הקריאות עם רקורסיה

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

האינטואיציה

עמוד באינדקס i והבט בספרה הבאה. אם היא 0, שום אות לא מתחילה כאן והמסלול הזה לא מניב שום פענוח. אחרת, אפשר לקרוא את הספרה הזאת כאות אחת ולספור את הפענוחים של השאר החל מ־i+1. אם היא יוצרת מספר בין 10 ל־26 יחד עם הספרה שאחריה, אפשר גם לקרוא את שתיהן כאות אחת ולספור החל מ־i+2. שתי האפשרויות נותנות אות ראשונה שונה, ולכן סכומי הפענוחים שלהן מצטברים ללא חפיפה. כש־i מגיע לסוף המחרוזת, סיימת פענוח שלם אחד, ולכן מחזירים 1.

עבור "2611": האות הראשונה היא 2 או 26. אחרי 2 האות הבאה חייבת להיות 6, כי 61 גדול מדי. שתי הענפים מסתיימים אז ב־1 1 או 11, ולכן הסכום הכולל הוא 2 × 2 = 4.

התשובה נכונה, אבל שום דבר לא נשמר בזיכרון. במחרוזת של אחדות כל קריאה מתפצלת לשתיים, והקריאות פועלות לפי כלל פיבונאצ'י, כך ש־45 אחדות דורשות בערך 5 × 10^9 קריאות. גם העבודה אינה מצטמצמת בהתאם לתשובה: עבור 44 אחדות ואחריהן 55 שלשות ואפס סופי 0, התשובה היא 0, ובכל זאת הרקורסיה עוברת על כל הפענוחים של האחדות דרך כל השלשות לפני שכל מסלול מסתיים בספרה האחרונה, כ־10^11 קריאות.

אלגוריתם

כתבו פונקציית עזר waysFrom(i) שסופרת את אפשרויות הפענוח של הספרות מהאינדקס i ועד הסוף.
אם i שווה לאורך של s, החזירו 1.
אם הספרה באינדקס i היא 0, החזירו 0.
התחילו עם waysFrom(i+1), אפשרויות הפענוח שבהן האות הבאה מיוצגת באמצעות ספרה אחת.
אם הספרות באינדקסים i ו-i+1 יוצרות מספר שאינו גדול מ-26, הוסיפו את waysFrom(i+2). החזירו את waysFrom(0).

def numDecodings(s):
    n = len(s)

    def ways_from(i):
        # The number of ways to decode s[i:].
        if i == n:
            return 1  # nothing left: one finished reading
        if s[i] == "0":
            return 0  # no letter code starts with 0
        ways = ways_from(i + 1)  # read one digit
        if i + 1 < n and int(s[i:i + 2]) <= 26:
            ways += ways_from(i + 2)  # read two digits, 10 to 26
        return ways

    return ways_from(0)

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

האינטואיציה

הרקורסיה שואלת שוב ושוב את אותה שאלה. ב־"11111", צריך את הספירה מאינדקס 3 אחרי 1 1 1, אחרי 11 1 ואחרי 1 11, והיא יוצאת זהה בכל פעם, כי היא תלויה רק בספרות מאינדקס 3 ואילך. שמור כל ספירה במערך memo בפעם הראשונה שאתה מחשב אותה, וקרא אותה משם לאחר מכן.

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

יש n מיקומים, וכל אחד מהם מחושב פעם אחת בעבודה קבועה, ולכן זמן הריצה הוא O(n). המערך memo ומחסנית הקריאות דורשים כל אחד O(n) מקום. הקריאות מקוננות כאן לעומק של 100 לכל היותר, שכל שפה מסוגלת להתמודד איתו.

אלגוריתם

צרו מערך memo עם מקום אחד לכל אינדקס, והגדירו את כולם ל־-1.
ב־waysFrom(i), החזירו 1 בסוף המחרוזת ואת memo[i] כשהוא אינו -1.
אחרת, ספרו כמו ברקורסיה הפשוטה: 0 עבור 0, אחרת waysFrom(i+1) ועוד waysFrom(i+2) כאשר שתי הספרות יוצרות מספר בין 10 ל־26.
שמרו את הספירה ב־memo[i], כולל אפס, והחזירו אותה.
החזירו את waysFrom(0).

def numDecodings(s):
    n = len(s)
    memo = [-1] * n  # memo[i]: ways to decode s[i:], -1 until worked out

    def ways_from(i):
        if i == n:
            return 1
        if memo[i] != -1:
            return memo[i]
        ways = 0
        if s[i] != "0":
            ways = ways_from(i + 1)  # read one digit
            if i + 1 < n and int(s[i:i + 2]) <= 26:
                ways += ways_from(i + 2)  # read two digits, 10 to 26
        memo[i] = ways
        return ways

    return ways_from(0)

מלמטה למעלה עם שני מונים

האינטואיציה

נהפוך את כיוון הרקורסיה ונספור קידומות. נסמן את מספר הפענוחים של i הספרות הראשונות בתור ways(i). האות האחרונה בפענוח כזה היא או הספרה שבאינדקס i-1 לבדה, שצריכה להיות ספרה מ־1 עד 9 ומשאירה ways(i-1) פענוחים לשאר, או שתי הספרות שבאינדקסים i-2 ו־i-1, שצריכות להרכיב מספר בין 10 ל־26 ומשאירות ways(i-2). לכן ways(i) הוא סכום החלקים שהתנאי שלהם מתקיים. לקידומת הריקה יש פענוח אחד, ההודעה הריקה, ולכן ways(0) = 1.

נעבור על "1203". אחרי 1 הספירה היא 1. אחרי 12 היא 2: 1 2 וגם 12. אי אפשר להשתמש ב־0 לבדו, ורק 20 תקין, כך שהספירה חוזרת לספירה שלפני 2, שהיא 1. אפשר להשתמש ב־3 לבדו, ו־03 אינו קוד, ולכן הספירה נשארת 1.

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

אלגוריתם

הגדר את twoBack = 0 ואת oneBack = 1, את מספר האפשרויות עבור הקידומת הריקה.
עבור כל אינדקס i, התחל את current ב־0, והוסף את oneBack אם הספרה i אינה 0.
אם i ≥ 1, הספרה i-1 אינה 0, והספרות i-1 ו־i יוצרות מספר שאינו גדול מ־26, הוסף את twoBack.
הזז קדימה: twoBack = oneBack, ואז oneBack = current.
אחרי הספרה האחרונה, החזר את oneBack.

def numDecodings(s):
    # ways(i) counts the readings of the first i digits; ways(0) = 1.
    two_back, one_back = 0, 1  # ways(i-1) and ways(i) before digit i is read
    for i in range(len(s)):
        current = 0
        if s[i] != "0":
            current = one_back  # digit i is a letter on its own
        if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
            current += two_back  # digits i-1 and i form one letter, 10 to 26
        two_back, one_back = one_back, current
    return one_back

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

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

התייחסות אל 0 כאל אות, או אל 06 בתור 6. אפס יכול לסיים רק את 10 או את 20, לכן ל-"30", ל-"100" ול-"06" יש 0 פענוחים.
בדיקת חלק בן שתי ספרות רק לפי התנאי ≤ 26. המספר 05 הוא 5, אבל הוא אינו קוד. יש לבדוק שהספרה הראשונה מבין השתיים אינה 0.
שימוש ב-0 כסימן לתא בזיכרון המטמון שעדיין לא חושב. במיקומים רבים יש באמת 0 פענוחים, ולכן התאים האלה לעולם לא נחשבים שמורים ומחושבים מחדש בכל ביקור. עבור 44 אחדות ואחריהן שלשות ואפס סופי 0, כל התאים הם 0, וחוזרים לכ-10^11 קריאות.
קריאת הספרה שלפני אינדקס 0. יש להגן על בדיקת שתי הספרות בתנאי i ≥ 1: ב-Python,‏ s[-1] קורא בשקט את הספרה האחרונה, ובשפות אחרות קוראים מחוץ למחרוזת.
המרת s למספר אחד. מאה ספרות אינן נכנסות לשום טיפוס מספר שלם, וההמרה מסירה אפסים מובילים, שמשנים את התשובה. עבדו ספרה אחר ספרה.
ב-Lua וב-R, המיקומים מתחילים ב-1, לכן סוף המחרוזת הוא במיקום n+1 ובדיקת שתי הספרות הראשונה היא במיקום 2.

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

מהי סיבוכיות הזמן של Decode Ways?

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

מה הקשר בין Decode Ways ל-Climbing Stairs?

שתיהן סופרות את מספר הדרכים לכסות קו בצעדים בגודל 1 ו-2. ב-Climbing Stairs כל צעד אפשרי, ולכן הספירה היא מספר פיבונאצ'י. ב-Decode Ways צעד של ספרה אחת דורש ספרה מ-1 עד 9, וצעד של שתי ספרות דורש מספר מ-10 עד 26, ולכן כל איבר בסכום מתווסף רק כאשר התנאי שלו מתקיים. מחרוזת של אחדות מאפשרת כל צעד, והספירות שלה הן בדיוק מספרי פיבונאצ'י.

איך מטפלים באפסים ב-Decode Ways?

המספר 0 לעולם לא יכול להיות אות בפני עצמו, ולכן הוא חייב להתחבר לספרה שלפניו, ורק 10 ו-20 הם קודים. בלולאה מלמטה למעלה, המשמעות היא ש-0 אינו מוסיף דבר במקרה של ספרה אחת, ומוסיף את הספירה מלפני שתי ספרות רק אחרי 1 או 2. 0 מוביל, שני אפסים ברצף, או 0 אחרי ספרה בין 3 ל-9 גורמים לתשובה להיות 0.

האם אפשר לפתור את Decode Ways בסיבוכיות מקום של O(1)?

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s = "2611"

צפוי

Decode Ways

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

נסו את שתי הקריאות עם רקורסיה

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

מלמטה למעלה עם שני מונים

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

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

בעיות דומות