Decode String
מחרוזת מקודדת מייצגת טקסט שחוזר על עצמו בצורה k[text], כלומר text נכתב k פעמים ברצף. קבוצות יכולות להופיע בתוך קבוצות אחרות, כך ש-2[a3[b]] מייצג את abbbabbb. כתבו פונקציה שמקבלת מחרוזת מקודדת s ומחזירה את המחרוזת המפוענחת.
אותיות שמחוץ לכל הסוגריים נשארות כפי שהן. כל מספר חזרות הוא מספר שלם חיובי שמופיע מיד לפני [ שלו, וספרות אינן מופיעות בשום מקום אחר.
פונקציה
- sstring
- המחרוזת המקודדת
- מחזירהstring
- המחרוזת המפוענחת
אילוצים
1 ≤ s.length ≤ 104sמכילה רק אותיות אנגליות קטנות, ספרות,[ו־].-
sהוא קידוד תקין: אחרי כל[מופיע מספר, ויש לו]תואם, ואף סוגריים אינם ריקים. - כל מספר
kמקיים1 ≤ k ≤ 300ואין לו אפסים מובילים. - סוגריים יכולים להיות מקוננים לעומק של 100 רמות לכל היותר.
- במחרוזת המפוענחת יש לכל היותר
5 × 104תווים.
דוגמאות
- קלט
- s = "2[ab]3[c]x"
- פלט
- "ababcccx"
- הסבר
2[ab]נותןababו-3[c]נותןccc. ה-xנמצא מחוץ לכל סוגריים, ולכן הוא מועתק כפי שהוא, מה שנותןababcccx.
- קלט
- s = "2[x3[yz]]"
- פלט
- "xyzyzyzxyzyzyz"
- הסבר
- פענחו קודם את החלק הפנימי:
3[yz]הואyzyzyz, ולכן גוף הקבוצה החיצונית הואxyzyzyz. כשכותבים אותו פעמיים, מתקבלxyzyzyzxyzyzyz.
- קלט
- s = "q10[w]e"
- פלט
- "qwwwwwwwwwwe"
- הסבר
- הספירה היא
10, שנקראת כשתי ספרות, ולכןwמופיע עשר פעמים ביןqל־e. קוד שקורא רק את הספרה שליד[יחזור עליה 0 פעמים.
+22 בדיקות נסתרות בשליחה
שאלת המשך
המחרוזת שפוענחה יכולה להיות ארוכה בהרבה מהקלט. איך תחזיר רק את התו במיקום i במחרוזת שפוענחה, בלי לבנות אותה, כאשר אורך המחרוזת שפוענחה יכול להגיע ל־10^18?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
אי אפשר לכתוב את
3[...]עד שיודעים מה נמצא בתוך הסוגריים, ובתוכם יכולים להיות קבוצות נוספות. איזו סוג של קבוצה אפשר תמיד לפענח מיד?אפשר להרחיב בבת אחת קבוצה שאין בתוכה קבוצות, לכן עבדו מבפנים החוצה. כשמגיע
], הקבוצה שהוא סוגר הושלמה, ואתם צריכים את הטקסט ואת הכמות שהמתינו לפני ה־[שלה.סרקו פעם אחת, תוך שמירה על הטקסט שנבנה עד כה ועל המספר שנקרא. כשמגיעים אל
[, דוחפים את שניהם למחסנית ומתחילים מחדש. כשמגיעים אל], שולפים אותם ומצרפים את הטקסט הנוכחי, כשהוא חוזר על עצמו, לטקסט שנשלף. בונים כל מספר ספרה אחר ספרה, כך שגם10וגם300יעבדו.
פתרון
המספר מופיע לפני הסוגריים, אבל אי אפשר לכתוב את העותקים עד שיודעים מה יש בתוכם, ובתוכם יכולים להיות קבוצות נוספות. לכן אפשר להרחיב קבוצה רק לאחר שכל הקבוצות שבתוכה הושלמו. כל אחת מהגישות שלהלן היא דרך להשלים קודם את הקבוצות הפנימיות ביותר: לכתוב מחדש את המחרוזת מבפנים החוצה, לתת לקריאה רקורסיבית להשלים את הקבוצה הפנימית לפני החיצונית, או לשמור את הקבוצות החיצוניות שטרם הושלמו במחסנית. להלן, n הוא אורך הקלט, m הוא אורך המחרוזת המפוענחת ו־d הוא העומק המרבי של הקינון.
הרחיבו את הקבוצה הפנימית ביותר, ואז חזרו על הפעולה
האינטואיציה
פענחו את המחרוזת כפי שהייתם עושים זאת על נייר. מצאו קבוצה שאין בתוכה קבוצה אחרת, כתבו במקומה את העותקים שלה והסתכלו שוב. ב־2[x3[yz]], הקבוצה 3[yz] אינה מכילה דבר, ולכן המחרוזת הופכת ל־2[xyzyzyz], והרחבה אחת נוספת נותנת את התשובה.
התו ] הראשון במחרוזת תמיד סוגר קבוצה כזאת. שום קבוצה אחרת לא נסגרה לפניו, לכן שום סוגריים לא יכולים להופיע בין התו הזה לבין [ שלו. התו [ הזה הוא הקרוב ביותר משמאלו, והמספר הוא רצף הספרות שמופיע ממש לפניו. החליפו את המספר, את הסוגריים ואת התוכן בגוף הקבוצה כשהוא כתוב k פעמים, וחזרו על הפעולה עד שלא נשאר אף ].
הפתרון הזה נכון, אבל בכל הרחבה נבנית מחדש המחרוזת כולה. כשיש b קבוצות והמחרוזת גדלה עד לכ־m תווים, מדובר בעד b × m העתקות תווים. בדיקה נסתרת עם כ־1,300 קבוצות זו לצד זו דורשת כ־25 מיליון העתקות כדי להפיק 27,688 תווים, בעוד שמעבר אחד על הקלט היה מספיק.
אלגוריתם
- מצא את התו
]הראשון במחרוזת. אם אין כזה, המחרוזת מפוענחת: החזר אותה. - התקדם שמאלה ממנו עד ל-
[הקרוב ביותר. הטקסט שביניהם הוא גוף הקבוצה. - התקדם עוד שמאלה מעל הספרות שלפני
[וקרא אותן כמספר החזרותk. - החלף את כל מה שמתחיל בספרה הראשונה ועד ל-
]בגוף הקבוצה כשהוא כתובkפעמים. - חזור לשלב 1.
def decodeString(s):
# Expand one innermost group at a time until no bracket is left.
while True:
close = s.find("]")
if close == -1:
return s
# The first ']' closes a group with no group inside it,
# and the nearest '[' to its left opens that group.
open_ = s.rfind("[", 0, close)
start = open_
while start > 0 and s[start - 1].isdigit():
start -= 1
times = int(s[start:open_])
s = s[:start] + s[open_ + 1:close] * times + s[close + 1:]ירידה רקורסיבית
האינטואיציה
המבנה הוא רקורסיבי: מחרוזת מקודדת היא רצף של אותיות וקבוצות, וגוף של קבוצה הוא בעצמו מחרוזת מקודדת. לכן כתבו פונקציה אחת, decode, שקוראת ממיקום משותף עד שהיא מגיעה אל ] שמסיים את הרמה שלה או אל סוף הקלט, ומחזירה את מה שקראה, לאחר פענוח.
כאשר decode נתקלת בספרה, היא קוראת את המספר כולו, מדלגת על [ וקוראת לעצמה כדי לפענח את גוף הקבוצה. הקריאה הזאת נעצרת ב-] התואם, מכיוון שכל ] פנימי יותר כבר נקרא על ידי קריאה פנימית יותר. הפונקציה הקוראת מדלגת על ], מוסיפה את גוף הקבוצה k פעמים וממשיכה לקרוא. עבור 2[x3[yz]], הקריאה החיצונית קוראת 2; הקריאה הבאה קוראת x ו-3; הקריאה השלישית מחזירה yz; הקריאה האמצעית מחזירה xyzyzyz; והקריאה החיצונית כותבת אותו פעמיים.
כל תו בקלט נקרא פעם אחת. העלות האמיתית היא העתקה: תו פלט מועתק פעם אחת עבור כל קבוצה שעוטפת אותו, ולכן זמן הריצה הוא O(n + m·d), כאשר עומק הקינון הוא d. גם הרקורסיה מגיעה לעומק d קריאות. זה בסדר עבור 100 רמות, אבל קלט עמוק מאוד עלול לגרום לגלישת מחסנית הקריאות: Python, למשל, נעצרת כברירת מחדל לאחר 1,000 קריאות מקוננות.
אלגוריתם
- יש לשמור מיקום אחד
pos, המשותף לכל הקריאות, שמתחיל בתו הראשון. decode()מבצעת לולאה כל עודposנמצא בתוך המחרוזת ואינו מצביע על].- כשנתקלים באות, יש להוסיף אותה ולהמשיך הלאה.
- כשנתקלים בספרה, יש לקרוא את המספר כולו
k, לדלג על[, לקרוא ל-decode()עבור הגוף, לדלג על], ולהוסיף את הגוףkפעמים. - יש להחזיר את מה שנבנה. הקריאה הראשונה מחזירה את המחרוזת המפוענחת.
def decodeString(s):
pos = 0
def decode():
# Read from pos up to the ']' that closes this level, or the end.
nonlocal pos
parts = []
while pos < len(s) and s[pos] != "]":
if s[pos].isdigit():
times = 0
while s[pos].isdigit():
times = times * 10 + int(s[pos])
pos += 1
pos += 1 # skip '['
inner = decode() # the group's body, fully decoded
pos += 1 # skip ']'
parts.append(inner * times)
else:
parts.append(s[pos])
pos += 1
return "".join(parts)
return decode()מעבר אחד עם מחסנית
האינטואיציה
הרקורסיה שומרת קטע טקסט אחד לא גמור לכל קבוצה פתוחה, בתוך מסגרות הקריאה שלה. במקום זאת, אפשר לשמור את הקטעים האלה במחסנית משלך ולקרוא את המחרוזת בלולאה אחת.
עקוב אחר שני דברים ברמה הנוכחית: current, הטקסט שפוענח עד כה, ו-count, המספר שנקרא. ספרה מוסיפה ל-count לפי count × 10 + digit, כך שמתקבלים הערכים הנכונים עבור 10 ו-300. [ פותח רמה: דחוף את current ואת count למחסנית, ואז אתחל מחדש את שניהם. אות מצטרפת ל-current. ] סוגר את הרמה: שלוף את הטקסט ואת המספר שנשמרו, ו-current הופך לטקסט שנשמר ואחריו count עותקים של current.
עקוב אחר 2[x3[yz]]. ב-[ הראשון דוחפים (ריק, 2). ה-x הופך את current ל-x. ב-[ השני דוחפים (x, 3), ו-yz ממלא מחרוזת current חדשה. ה-] הראשון שולף (x, 3), ולכן current הופך ל-xyzyzyz. ה-] האחרון שולף (ריק, 2), ו-current הופך ל-xyzyzyzxyzyzyz.
קבוצות נסגרות בסדר הפוך לסדר שבו נפתחו, ולכן ראש המחסנית הוא תמיד הרמה שאליה ] חוזר. העבודה תואמת לרקורסיה, O(n + m·d), אך קינון עמוק רק מגדיל רשימה, ולעולם לא את מחסנית הקריאות.
אלגוריתם
- מתחילים עם מחסנית ריקה, עם
currentריק ועםcount = 0. - כשמופיעה ספרה, מגדירים
count = count × 10 + digit. - כשמופיע
[, דוחפים את הזוג (current,count) למחסנית, ואז מאפסים אתcurrentלערך ריק ואתcountל־0. - כשמופיעה אות, מוסיפים אותה ל־
current. - כשמופיע
], שולפים את (before,k) ומגדירים אתcurrentלערךbeforeואחריוcurrentשמופיעkפעמים. - אחרי התו האחרון, מחזירים את
current.
def decodeString(s):
stack = [] # one entry per open '[': (the text before it, its count)
current = [] # pieces of the text at the current level
count = 0
for ch in s:
if ch.isdigit():
count = count * 10 + int(ch) # counts can have several digits
elif ch == "[":
stack.append((current, count))
current, count = [], 0
elif ch == "]":
before, times = stack.pop()
before.append("".join(current) * times)
current = before
else:
current.append(ch)
return "".join(current)
מלכודות ומקרי קצה
רוב התשובות השגויות נובעות מקריאה לא נכונה של הספירה או מאי-הבנה של המקום שאליו מגיע הטקסט שנשמר.
- קריאת ספרה אחת כאילו היא הספירה כולה. ב-
q10[w]eהספירה היא 10. קוד שלוקח רק את הספרה שלפני[חוזר עלw0 פעמים. - שוכחים לאפס את
countל-0 אחרי שדוחפים אותו. הספרות של הקבוצה הבאה מתווספות למספר הישן, ולכן2[a3[b]]קורא את הספירה הפנימית כ-23. - מוסיפים את העותקים לפני הטקסט שנשמר. כשמגיעים ל-
], התוצאה היא הטקסט שלפני הקבוצה ואחריו העותקים, ולכןab2[c]הואabcc, ולאccab. - מאבדים אותיות ברמה העליונה. ה-
xשב-2[ab]3[c]xנמצא מחוץ לכל סוגריים ועדיין שייך לתשובה. - משרשרים תו אחד בכל פעם למחרוזת ארוכה ובלתי ניתנת לשינוי. כל שרשור עלול להעתיק את המחרוזת כולה, וכך תשובה באורך 50,000 תווים עלולה להפוך למיליארדי העתקות. אספו חלקים ברשימה או בונה מחרוזות.
שאלות נפוצות4
מהי סיבוכיות הזמן של Decode String?
קריאת הקלט היא O(n). בניית הפלט מעתיקה כל תו פעם אחת לכל קבוצה שהוא נמצא בתוכה, ולכן הסך הכול הוא O(n + m·d), כאשר m הוא האורך לאחר הפענוח ו־d הוא עומק הקינון. כאשר כל המספרים הם לפחות 2, כל קבוצה היא לכל היותר באורך חצי מהקבוצה שמקיפה אותה, ולכן מספר ההעתקות נשאר קטן מ־2m. שום גישה לא יכולה להיות יעילה יותר מ־O(m), כי התשובה עצמה מכילה m תווים.
האם כדאי לפתור את Decode String באמצעות רקורסיה או באמצעות מחסנית?
שניהם מבצעים את אותה עבודה. רקורסיה פועלת ישירות לפי הפורמט, מכיוון שהגוף של קבוצה הוא בעצמו מחרוזת מקודדת, ולעיתים קרובות היא הדרך המהירה ביותר לכתוב פתרון בריאיון. גרסת המחסנית עושה את אותו הדבר בלולאה אחת ושומרת את הרמות החיצוניות שטרם הושלמו ברשימה, כך שקינון עמוק מאוד לא יגרום לגלישה במחסנית הקריאות. אם המראיין שואל על קלט המקונן באלפי רמות, המחסנית היא התשובה.
איך מטפלים בספירות עם יותר מספרה אחת?
בנו את המספר תוך כדי קריאתו: התחילו ב־0, ולכל ספרה הגדירו count = count × 10 + digit. כשהתו [ מגיע, המספר הושלם, ולכן 300[a] נותן 300. אפסו את המונה מיד לאחר הוספתו למחסנית, אחרת הספרות של הקבוצה הבאה יתווספו אליו.
למה המחסנית שומרת את הטקסט שהופיע לפני כל סוגר?
כש־[ נפתחת, הטקסט שפוענח עד כה ברמה הזאת עדיין לא הושלם: העותקים של הקבוצה עדיין צריכים לבוא אחריו. דחיפתו שומרת עליו בבטחה בזמן שפענוח הגוף מתחיל ממחרוזת ריקה. כשמגיע ] התואם, שליפתו מחזירה את הטקסט הזה, ואתה מוסיף אליו את העותקים.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def decodeString(s):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
s = "2[ab]3[c]x"
צפוי
"ababcccx"