Decode Ways
הודעה באותיות גדולות קודדה באמצעות A = 1, B = 2 וכן הלאה עד Z = 26, והקודים נכתבו ללא מפרידים. בהינתן מחרוזת הספרות s, החזר כמה הודעות יכלו ליצור אותה.
אות נקראת מתוך ספרה אחת או שתי ספרות סמוכות, וקוד לעולם אינו מתחיל ב־0: 06 אינו 6, ו־0 בודד אינו אות. אם אין דרך לקרוא את המחרוזת, החזר 0.
פונקציה
- sstring
- מחרוזת הספרות לפענוח
- מחזירהinteger
- מספר הודעות האותיות שמקודדות ל-s
אילוצים
1 ≤ s.length ≤ 100sמכיל רק את הספרות0עד9, והוא עשוי להתחיל ב-0.- לכל קידומת ולכל סיומת של
sיש פחות מ־231קריאות, ולכן התשובה וכל ספירה שתבנו בדרך נכנסות למספר שלם מסומן בן 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אינו קוד, ולכן אף הודעה לא נותנת את המחרוזת הזאת.
שאלת המשך
מה אם s יכול להכיל גם את *, שמייצג כל ספרה מ־1 עד 9? האם תוכל לספור את הקריאות בזמן O(n), מודולו 10^9+7?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
התבוננו בספרה הראשונה בלבד. בכמה דרכים אפשר לקרוא את האות הראשונה, ומה נשאר מהמחרוזת אחרי כל בחירה?
מספר הקריאות של שאר המחרוזת תלוי רק במקום שבו היא מתחילה, ולא בדרך שבה הגעת אליו. ספור כל נקודת התחלה פעם אחת והשתמש שוב במספר.
נסמן את מספר אפשרויות הפענוח של
iהספרות הראשונות ב־ways(i), כאשרways(0) = 1. נוסיף אתways(i-1)כאשר הספרהi-1אינה0, ונוסיף אתways(i-2)כאשר שתי הספרות שלפני המיקוםiיוצרות מספר בין 10 ל־26. צריך רק את שתי הספירות האחרונות.
פתרון
כל ספרה היא אות בפני עצמה או מצטרפת לשכנה שלה, ולכן מספר האפשרויות לקריאה גדל כמו מספרי פיבונאצ'י: ל־45 אחדות יש 1836311903 אפשרויות. אין טעם למנות אותן, אבל הדרכים להשלים קריאה תלויות רק במיקום שאליו הגענו, ולכן צריך לספור כל מיקום פעם אחת. 0 יכול להופיע רק בסוף של 10 או 20.
נסה את שתי הקריאות עם רקורסיה
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
במיקום i, 0 אינו מתחיל אף אות, ולכן המסלול אינו מניב פענוחים. אחרת קוראים ספרה אחת וסופרים את האפשרויות שנותרו החל מ־i+1; אם שתי הספרות יוצרות מספר בין 10 ל־26, קוראים גם את שתיהן וסופרים החל מ־i+2. שתי האפשרויות מניבות אותיות ראשונות שונות, ולכן מספרי הפענוחים שלהן מתחברים ללא חפיפה, והגעה לסוף משלימה פענוח אחד.
שום דבר לא נשמר, ולכן הקריאות פועלות לפי כלל פיבונאצ'י: 45 ספרות 1 דורשות בערך 5 × 10^9 קריאות. תשובה של 0 אינה מהירה יותר: 44 ספרות 1, 55 ספרות 3 וספרת 0 אחרונה דורשות בערך 10^11 קריאות, משום שכל פענוח של הספרות 1 מסתיים בכישלון רק בספרה האחרונה.
אלגוריתם
waysFrom(i)סופרת את דרכי הקריאה של הספרות החל מהאינדקסi.- בסוף המחרוזת, החזירו 1. במקרה של
0, החזירו 0. - אחרת החזירו את
waysFrom(i+1), ובנוסף אתwaysFrom(i+2)כאשר הספרותiו-i+1יוצרות מספר שאינו גדול מ-26. - התשובה היא
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 ואילך. שמור כל ספירה בפעם הראשונה שאתה מחשב אותה, וסמן משבצות שטרם חושבו ב־-1, כי 0 הוא ספירה אמיתית.
יש n מיקומים, וכל אחד מחושב פעם אחת בעבודה קבועה: זמן O(n). הזיכרון לממואיזציה ומחסנית הקריאות צורכים O(n) מקום, עד לעומק של 100 קריאות.
אלגוריתם
- מלאו את
memoבערך-1, משבצת אחת לכל אינדקס. - ב־
waysFrom(i), החזירו 1 בסוף המחרוזת ואתmemo[i]כשהוא אינו-1. - אחרת, ספרו כמו ברקורסיה הפשוטה, שמרו את הספירה ב־
memo[i], כולל אפס, והחזירו אותה.
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)מלמטה למעלה עם שני מונים
האינטואיציה
במקום זאת, ספרו קידומות. נסמן ב־ways(i) את מספר הפענוחים של i הספרות הראשונות. האות האחרונה היא או הספרה i-1 לבדה, שצריכה להיות בין 1 ל־9 ומשאירה ways(i-1) פענוחים, או הספרות i-2 ו־i-1 יחד, שחייבות להרכיב מספר בין 10 ל־26 ולהשאיר ways(i-2) פענוחים. מחברים את החלקים שהתנאי שלהם מתקיים. לקידומת הריקה יש פענוח אחד, ולכן ways(0) = 1.
עבור "1203", הספירות הן 1, 2, ואז חוזרות ל־1 ב־0, כי רק 20 אפשרי, והוא משאיר את הספירה שלפני ה־2. ה־3 עומדת לבדה, ולכן הספירה נשארת 1. כל ספירה מתבססת על זו שלפניה בשני צעדים, ולכן שני משתנים מחליפים את הטבלה: זמן O(n), מקום O(1).
אלגוריתם
- הגדר את
twoBack = 0ואתoneBack = 1, מספר האפשרויות עבור הקידומת הריקה. - עבור כל אינדקס
i, הגדר אתcurrentל-oneBackאם הספרהiאינה0, אחרת ל-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. ל-"30","100"ו-"06"יש 0 קריאות. - בדיקת קטע בן שתי ספרות באמצעות
≤ 26בלבד.05הוא 5 כמספר אבל אינו קוד, לכן בדקו שהספרה הראשונה שלו אינה0. - סימון משבצות זיכרון לא ידועות ב-0. מיקומים עם 0 קריאות לעולם אינם נחשבים מאוחסנים: עבור 44 ספרות 1, 55 ספרות 3 וספרת
0סופית, חוזרים לכ-10^11קריאות. - קריאת הספרה שלפני האינדקס 0. הגנו על בדיקת שתי הספרות באמצעות
i ≥ 1; ב-Python,s[-1]קורא בשקט את הספרה האחרונה. - הפיכת
sלמספר אחד. מאה ספרות אינן מתאימות לאף סוג מספר שלם, והאפסים המובילים שמשנים את התשובה הולכים לאיבוד.
שאלות נפוצות3
מהי סיבוכיות הזמן של 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. הוא מוסיף את הספירה מלפני שתי ספרות רק אחרי 1 או 2, ובכל מקרה אחר אינו מוסיף דבר. 0 בתחילת הרצף, שני אפסים ברצף, או 0 אחרי 3 עד 9 נותנים 0.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def numDecodings(s):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
s = "2611"
הפלט הצפוי
4