Generate Parentheses
מחרוזת של סוגריים היא תקינה כאשר, בקריאה משמאל לימין, מספר ה־) לעולם אינו עולה על מספר ה־(, ושני המספרים שווים בסוף. לכן (())() תקינה, ואילו ())( אינה תקינה: התו השלישי שלה סוגר זוג שמעולם לא נפתח.
מקבלים מספר שלם n. יש להחזיר את כל המחרוזות התקינות שמורכבות מ־n סוגריים פותחים ו־n סוגריים סוגרים, ממוינות בסדר לקסיקוגרפי, כאשר ( מופיע לפני ).
פונקציה
- ninteger
- מספר זוגות הסוגריים
- מחזירהstring-array
- כל מחרוזת תקינה של n זוגות, בסדר לקסיקוגרפי
אילוצים
1 ≤ n ≤ 8- עבור
n = 8התשובה מכילה 1,430 מחרוזות.
דוגמאות
- קלט
- n = 3
- פלט
- ["((()))", "(()())", "(())()", "()(())", "()()()"]
- הסבר
- אפשר לסדר שלושה זוגות בחמש דרכים תקינות.
((()))פותח את שלושתם לפני שסוגרים אחד מהם, ומכיוון ש-(מופיע ראשון בסדר המיון, הוא מוביל את הרשימה;()()()סוגר כל זוג מיד, ומופיע אחרון.
- קלט
- n = 1
- פלט
- ["()"]
- הסבר
- לזוג אחד יש סידור תקין יחיד. המחרוזת היחידה האחרת המורכבת מ־
(אחד ומ־)אחד היא)(, שבה הסוגר נסגר לפני שמשהו נפתח.
+10 בדיקות נסתרות בשליחה
שאלת המשך
האם תוכל לספור את המחרוזות התקינות עבור n זוגות בלי ליצור אותן?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
קרא מחרוזת משמאל לימין וספור את הזוגות הפתוחים. מה השתבש אם הספירה הזאת תרד מתחת לאפס?
בנה את המחרוזת תו אחד בכל פעם. אפשר להוסיף
(כל עוד הוספת פחות מ-nכאלה, ו-)כל עוד הוספת פחות)מאשר(. תמיד אפשר להשלים מחרוזת שנבנתה בדרך זו.בצעו רקורסיה עם שני מונים,
openedו־closed. נסו את הענף של(לפני הענף של), הסירו כל תו לאחר שהקריאה שלו חוזרת, ושמרו את המחרוזת כשהיא מגיעה לאורך2n. הניסיון של(תחילה שומר על פלט ממוין.
פתרון
רק חלק קטן מהמחרוזות באורך 2n הן תקינות: 5 מתוך 64 המחרוזות עבור n = 3, ו־1,430 מתוך 65,536 עבור n = 8. הרעיון שפותר את הבעיה הוא לבנות את המחרוזת משמאל לימין ולהוסיף בכל פעם רק תו שמשאיר אותה תקינה, כך שהחיפוש לעולם לא נכנס לענף שאי אפשר להשלים. שני מונים קובעים מה מותר: כמה תווי ( הצבת, וכמה תווי ). ניסיון להוסיף ( לפני ) בכל צעד גורם לכך שהמחרוזות מתקבלות כשהן כבר ממוינות.
בנו כל מחרוזת, ואז בדקו אותה
האינטואיציה
הדרך הישירה היא למלא את 2n המקומות בכל דרך אפשרית ולשמור את המחרוזות שהן תקינות. בכל מקום מופיע ( או ), ולכן יש 2^(2n) = 4^n מחרוזות. פונקציה רקורסיבית מציבה ( במקום הבא, קוראת לעצמה, ואז מציבה שם ) וקוראת לעצמה שוב, וכל מחרוזת שהושלמה עוברת בדיקה.
הבדיקה עוברת על המחרוזת תוך מעקב אחר מאזן: מוסיפים 1 עבור (, ומחסרים 1 עבור ). המחרוזת תקינה אם המאזן לעולם אינו יורד מתחת ל-0 ומסתיים ב-0. ירידה מתחת ל-0 פירושה שיש ) בלי סוגר פתוח לסגור, כמו התו השלישי ב-())(.
ניסיון להציב ( לפני ) בכל מקום מציג את המחרוזות בסדר לקסיקוגרפי, כי ( מופיע לפני ) במיון. לכן המחרוזות שנשמרות כבר ממוינות.
העלות היא 4^n מחרוזות, שכל אחת מהן נבדקת ב-O(n). עבור n = 8 מדובר ב-65,536 מחרוזות עבור 1,430 תשובות, כך שכ-98% מהעבודה נזרקים לפח. התהליך מסתיים כאן כי n הוא לכל היותר 8, אבל הוא גדל פי ארבעה עם כל זוג נוסף, והוא ממשיך לבנות מחרוזות שמתחילות ב-) אף על פי שהתו הראשון כבר פוסל אותן.
אלגוריתם
- שמור מאגר של
2nתווים ורשימה עבור התשובות. - כתוב
fill(pos). אםposשווה ל-2n, בדוק את המאגר ושמור אותו אם הוא תקין. - אחרת, הצב
(במיקוםposוקרא ל-fill(pos + 1), ואז הצב שם)וקרא לה שוב. - כדי לבדוק מחרוזת, הוסף 1 עבור כל
(והפחת 1 עבור כל). דחה אותה ברגע שהמאזן יורד מתחת ל-0, או אם הוא אינו מסתיים ב-0. - קרא ל-
fill(0)והחזר את המחרוזות שנשמרו, כשהן כבר ממוינות.
def generateParenthesis(n):
result = []
path = []
def is_balanced(text):
balance = 0
for ch in text:
balance += 1 if ch == "(" else -1
if balance < 0:
return False # a ")" with nothing open to close
return balance == 0
def fill():
if len(path) == 2 * n:
text = "".join(path)
if is_balanced(text):
result.append(text)
return
for ch in "()": # "(" first keeps the output sorted
path.append(ch)
fill()
path.pop()
fill()
return resultחזרה לאחור במספרי הפתיחה והסגירה
האינטואיציה
העבר את הבדיקה אל תוך הבנייה. קידומת עדיין יכולה לגדול למחרוזת תקינה בדיוק כאשר מתקיימים שני כללים: היא משתמשת בלא יותר מ־n סוגריים פותחים, ומספר הסוגריים ) בה לעולם אינו גדול ממספר הסוגריים (. לכן בכל שלב אפשר להוסיף ( כל עוד opened < n, ולהוסיף ) כל עוד closed < opened. כשהמחרוזת מגיעה לאורך 2n, שתי הכמויות הן n והמחרוזת תקינה, ואין עוד מה לבדוק.
הנה כל העץ עבור n = 2. מהמחרוזת הריקה מותר להוסיף רק (, כי עדיין אין סוגריים פתוחים. אחרי ( שתי האפשרויות מותרות. בענף ((, הערך של opened הוא כבר 2, ולכן אפשר להוסיף רק ), פעמיים, וכך מתקבלת (()). בענף () אין סוגריים פתוחים, ולכן אפשר להוסיף רק (, ואז ), וכך מתקבלת ()(). כל ענף מסתיים בתשובה: החיפוש לעולם אינו בונה מחרוזת שעליו להשליך.
אף תשובה אינה מתפספסת. כל קידומת של מחרוזת תקינה מצייתת לשני הכללים, ולכן החיפוש לעולם אינו דוחה את התו שהמחרוזת זקוקה לו בשלב הבא, וכל מחרוזת נוצרת פעם אחת, כי התווים שלה מתווים מסלול יחיד בעץ. הסדר עובד כמו בגישה הראשונה: שתי מחרוזות נבדלות לראשונה במקום שבו המסלולים שלהן מתפצלים, והענף ( נבדק שם קודם.
כל עלה הוא תשובה, ומספר התשובות עבור n זוגות הוא מספר קטלאן C(n), שגדל כמו 4^n / (n^1.5 √π). כל צומת פנימי נמצא בדרך לעלה אחד לפחות, ולכן יש לכל היותר 2n צמתים פנימיים לכל תשובה, והעתקת תשובה עולה O(n). הסיבוכיות הכוללת היא O(n × C(n)) = O(4^n / √n): עבור n = 8, נבנות ישירות 1,430 מחרוזות במקום לבדוק 65,536.
אלגוריתם
- שמרו את המחרוזת שנבנית ואת שני המונים,
openedו־closed, שניהם 0. - אם אורך המחרוזת הוא
2n, שמרו עותק שלה והחזירו. - אם
opened < n, הוסיפו(, קראו לפונקציה רקורסיבית עםopened + 1, והסירו אותו. - אם
closed < opened, הוסיפו), קראו לפונקציה רקורסיבית עםclosed + 1, והסירו אותו. - התחילו מהמחרוזת הריקה והחזירו את המחרוזות שנשמרו, שכבר ממוינות כי מנסים תחילה את
(.
def generateParenthesis(n):
result = []
path = []
def backtrack(opened, closed):
if len(path) == 2 * n:
result.append("".join(path))
return
# "(" sorts before ")", so trying it first keeps the output sorted
if opened < n:
path.append("(")
backtrack(opened + 1, closed)
path.pop()
if closed < opened: # only close a pair that is open
path.append(")")
backtrack(opened, closed + 1)
path.pop()
backtrack(0, 0)
return result
מלכודות ומקרי קצה
הכללים מסתכמים בשתי השוואות, ולכן הבאגים מסתתרים בהשוואות האלה ובסדר של שני הענפים.
- מתן אפשרות ל-
)כאשרclosed < nבמקוםclosed < openedיוצר מחרוזות כמו())(, שסוגרות זוג שלא נפתח מעולם. - בדיקה שלפיה יש במחרוזת אותו מספר של
(ושל)מקבלת את)(. המאזן צריך להישאר 0 או יותר בכל שלב, ולא רק בסוף. - ניסיון של
)לפני(יוצר את המחרוזות הנכונות בסדר הפוך, וההשוואה לתשובה הממוינת נכשלת. - שמירת המאגר המשותף במקום עותק שלו, בשפה שבה רשימות או בוני מחרוזות ניתנים לשינוי: כל תשובה שנשמרה מפנה אז לאותו מאגר, שהחזרה לאחור מרוקנת שוב.
- הקצאת מערך תוצאות קבוע בגודל
2nתשובות, או כל ניחוש קטן אחר: עבורn = 8יש 1,430 תשובות. הגדילו את המערך או חשבו תחילה את מספר קטלן.
שאלות נפוצות4
מהי סיבוכיות הזמן של Generate Parentheses?
פתרון החזרה לאחור מפיק מספר קטלאן C(n) = (2n)! / ((n+1)! n!) של מחרוזות, שגדל כמו 4^n / (n^1.5 √π). כל מחרוזת היא באורך 2n, והחיפוש לעולם אינו מבזבז ענף, ולכן זמן הריצה הכולל הוא O(4^n / √n). המקום הנוסף הוא O(n) עבור המחרוזת הנוכחית ומחסנית הקריאות, בנוסף לפלט.
כמה מחרוזות סוגריים תקינות יש עבור n זוגות?
מספר קטלאני מדויק עבור n: 1, 2, 5, 14, 42, 132, 429 ו־1,430 עבור n מ־1 עד 8. דרך אחת לראות זאת: כל מחרוזת תקינה היא ( + A + ) + B, כאשר את ( הראשון מתאים ) הזה, ו־A ו־B תקינים, וביניהם יש n-1 זוגות. סכימה על פני הגודל של A נותנת את נוסחת הנסיגה של המספרים הקטלאניים.
למה closed < opened מבטיח מחרוזת תקינה?
מחרוזת משתבשת בדיוק כאשר מגיע ) בלי ( שלא הותאם לפניו, כלומר כאשר מספר ה-) עולה על מספר ה-(. התרת ) רק כל עוד closed < opened מונעת זאת לחלוטין, והתרת ( רק כל עוד opened < n גורמת לשני המספרים להגיע ל-n באורך 2n. יחד, שני הכללים מתארים כל קידומת של מחרוזת תקינה.
האם אפשר לפתור את יצירת הסוגריים בלי רקורסיה?
כן. שמור מחסנית של מצבים חלקיים, שכל אחד מהם הוא מחרוזת עם שני המונים שלה, והרחב מצב באמצעות אותם שני כללים. אם תדחוף את ההרחבה ) לפני ההרחבה (, ההרחבה ( תישלף ראשונה והפלט יישאר ממוין. העבודה זהה; ניהול המצב עובר ממחסנית הקריאות למחסנית משלך.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def generateParenthesis(n):
# כתבו כאן את הקודמקרה 1
מקרה 2
קלט
n = 3
צפוי
["((()))", "(()())", "(())()", "()(())", "()()()"]