אתגר תכנותי Decode ways - פענוח הדרכים

תיאור הבעיה

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

• "1" → "A", "2" → "B", …, "26" → "Z"

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

לדוגמה, "12239" יכולה להיות מפוענחת ב-5 דרכים שונות. כולם תקפות:

• "1" "2" "2" "3" "9"
• "1" "2" "23" "9"
• "1" "22" "3" "9"
• "12" "2" "3" "9"
• "12" "23" "9"

שימוש ב-Brute Force לפתרון הבעיה

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

• אפשרות 1: לוקחים ספרה אחת (במידה והיא מייצגת אות חוקית, כלומר מספר בין 1 ל-9).
• אפשרות 2: לוקחים זוג ספרות (אם הן יוצרות מספר תקף בין 10 ל-26).

לדוגמה, נפענח את "12239" צעד אחר צעד בגישת Brute force:

1. בשלב ראשון מתחילים מ- "12239":

   • אפשרות 1: לקחת את "1", ולהעביר לשלב הבא את "2239".

   • אפשרות 2: לקחת את "12", ולהעביר לשלב הבא את "239".

   

2. נטפל ב-"2239" מהשלב הראשון:

   • אפשרות 1: לקחת את "2" ולהעביר לשלב הבא את "239".

   • אפשרות 2: לקחת את "22" ולהעביר לשלב הבא את "39".

   

3. נטפל ב-"239":

   • אפשרות 1: לקחת את "2" ולהעביר לשלב הבא את "39".

   • אפשרות 2: לקחת את "23" ולהעביר לשלב הבא את "9".

   

4. נטפל ב-"39":

   • אפשרות 1: לקחת את "3" ולהעביר לשלב הבא את "9".

   • אפשרות 2: "39" אינו ניתן לפענוח (גבוה מ-26) אז לא נמשיך עם אפשרות זו.

5. מאפשרות 1 בשלב 4 נשאר "9", שאותו ניתן לפענח כי הוא ספרה בודדת בין 1 ל-9 (כולל), וזהו אי אפשר להמשיך לפרק. נסמן "V" כי מצאנו את אחד הפתרונות: "1", "2", "2", "3", "9" כפי שניתן לראות אם עוקבים אחר הענפים המסתעפים מן השורש.

   

6. נחזור ל-"9" מאפשרות 2 של שלב 3, ונראה שאין לאן להמשיך. נסמן בוי כי מצאנו אפשרות פירוק נוספת: "1", "2", "23", "9".

   

7. נחזור ל-"39" מאפשרות 1 בצעד 3:

   • אפשרות 1: לקחת את "3" ולהעביר לשלב הבא את "9".

   • אפשרות 2: "39" אינו ניתן לפענוח (גבוה מ-26) אז לא נמשיך עם אפשרות זו.

8. נטפל ב-"9" מצעד 7. לא ניתן לפרק אותו מעבר לזה אז נסמן וי כי מצאנו פתרון נוסף: "1", "22", "3", "9".

   

9. נחזור ל-"239" מאפשרות 2 בצעד 1, ונחזור שוב על הפירוק אותו כבר עשינו בצעד השלישי מה שיוביל למציאת אפשרות פירוק נוספת של המחרוזת המקורית.

   

הבעיה עם גישת ה- brute force לפתרון הבעיה היא שאנחנו מוצאים את עצמנו חוזרים על אותם החישובים. לדוגמה, את "239" אנחנו מפענחים פעמיים. מה שיותר יעיל לעשות הוא לצבור את החישובים שכבר עשינו לתוך טבלה, ובמידה ואנחנו נפגשים בהמשך בחישוב שכבר עשינו, לשלוף את התוצאות מתוך הטבלה במקום לחשב מחדש. את זה בדיוק מאפשר לנו לעשות פתרון מבוסס תכנות דינאמי.

פתרון מבוסס תכנות דינאמי (Dynamic Programming)

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

מימוש הפתרון באמצעות טבלת DP יראה כך:

def is_valid(s: str) -> bool:
    return 1 <= int(s) <= 26


def decode_ways(s: str) -> int:
    # Validate input: empty string or starting with "0" is not decodable.
    if not s or s[0] == "0":
        return 0

    len_s = len(s)

    # Initialize Dynamic Programming table
    ways = [0] * (len_s + 1)

    # Initialize first 2 items
    ways[0] = 1
    ways[1] = 1

    for idx in range(2, len_s + 1):
        # Check if a single digit is valid.
        if is_valid(s[idx-1:idx]):
            ways[idx] += ways[idx-1]
        # Check if two-digit is valid.
        if idx > 1 and is_valid(s[idx-2:idx]):
            ways[idx] += ways[idx-2]
    
    return ways[len_s]

נבדוק:

# Test cases:
print(decode_ways("012"))  # -> 0
print(decode_ways("12"))   # -> 2: ("1", "2") and ("12")
print(decode_ways("226"))  # -> 3: ("2", "2", "6"), ("22", "6"), ("2", "26")
print(decode_ways("12259"))  # -> 5

הערכת מורכבות הפתרון

מורכבות הזמן היא O(n) כי עוברים על כל ספרה פעם 1 בלבד.

מורכבות המקום היא O(n) כי אורך טבלת התכנות הדינאמי הוא n+1.

פתרון יעיל עוד יותר שעדיין מבוסס על תכנות דינאמי

פתרון יעיל עוד יותר חוסך את מורכבות המקום הנובעת משימוש בטבלת תכנות דינאמי על ידי כך שהוא משתמש במקום בטבלת DP בשני משתנים בלבד:

• אחד המחזיק את התוצאה לפני האחרונה
• שני המחזיק את התוצאה השנייה לפני האחרונה

def decode_ways(s="") -> int:
    # Validate
    if not s or s[0] == "0":
        return 0
    
    len_s = len(s)
    
    # Instead of DP use two variables to store the last two values
    prev, cur = 1, 1  # Base cases: dp[0] = dp[1] = 1
    
    for idx in range(2, len_s + 1):
        # Cache the current value of dp[i-1] before computing dp[i]
        cached_cur = cur

        # Compute dp[i] (stored in cur) for the current index
        cur = 0
        if s[idx - 1] != "0":  # Single digit check
            cur += cached_cur
        if 10 <= int(s[idx - 2 : idx]) <= 26:  # Two-digit check
            cur += prev

        # Update dp[i-2] for the next iteration: it becomes the old dp[i-1]
        prev = cached_cur

    return cur

שימוש בשני משתנים במקום בטבלת תכנות דינאמי מאפשר להפחית את השימוש בזיכרון מ-O(n) ל-O(1) תוך ניצול העובדה שכל מה שאנחנו צריכים לעשות הוא לחזור אל התוצאות של שני הצעדים הקודמים בלבד על מנת לחשב את הצעד הנוכחי.

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

תכנות דינמי מלמטה למעלה ובחזרה - מדריך לתכנות דינאמי שמתחיל מהבסיס

אתגר תכנותי: שודד הבתים

פתרון בעיית הקיטבג knapsack באמצעות תכנות דינמי

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים