Longest Valid Parentheses
נתונה לך מחרוזת s שמורכבת רק מהתווים ( ו-). מצא את תת-המחרוזת הארוכה ביותר (רצף של תווים עוקבים) שהיא תקינה: כל ( שבה נסגרת על ידי ) שמופיעה אחריה, והזוגות מקוננים כראוי, כמו ב-(()()). החזר את האורך של תת-המחרוזת הזאת, או 0 אם אפילו () לא מופיע.
פונקציה
- sstring
- מחרוזת של התווים ( ו-)
- מחזירהinteger
- האורך של תת־המחרוזת התקינה הארוכה ביותר, או 0 אם אין כזאת
אילוצים
1 ≤ s.length ≤ 6 × 104- כל תו ב-
sהוא(או).
דוגמאות
- קלט
- s = "()(())"
- פלט
- 6
- הסבר
- כל המחרוזת בנויה היטב:
()ואחריו(()). שתי חתיכות הבנויות היטב זו לצד זו יוצרות חתיכה אחת הבנויה היטב, לכן התשובה היא כל 6 התווים.
- קלט
- s = "())((())"
- פלט
- 4
- הסבר
- ל-
)באינדקס 2 אין סוגר תואם, לכן שום תשובה לא יכולה לחצות אותו, וה-(באינדקס 3 לעולם אינו נסגר. הקטע הארוך ביותר הוא(())מאינדקס 4 עד 7, באורך 4, והוא ארוך יותר מה-()שבהתחלה.
- קלט
- s = "))(("
- פלט
- 0
- הסבר
- שני
)מופיעים לפני שני(, ולכן אף(לא נסגר. אף תת־מחרוזת אינה תקינה, והתשובה היא 0.
שאלת המשך
האם תוכל גם לדווח היכן מתחילה תת־המחרוזת התקינה הארוכה ביותר, ולבחור את השמאלית ביותר כאשר לכמה מהן יש אותו אורך?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
קרא תת־מחרוזת משמאל לימין ושמור על מאזן: +1 עבור
(, -1 עבור). מה קורה למאזן בתת־מחרוזת תקינה, ומה מספר לך)שמוריד אותו מתחת לאפס על כל תת־מחרוזת שחוצה אותו?שמור מחסנית של האינדקסים של תווי
(שעדיין פתוחים. כש-)סוגר את התו שבראש המחסנית, הרצף התקין שמסתיים כאן מתחיל מיד אחרי האינדקס שנמצא כעת בראש המחסנית. מה צריך להיות במחסנית כששום דבר אינו פתוח?התחל את המחסנית עם -1, האינדקס שמיד לפני המחרוזת. דחוף את האינדקס של כל
(. כשמגיעים ל־), שלוף; אם המחסנית כעת ריקה, אי אפשר לעולם להתאים את ה־)הזה, לכן דחוף את האינדקס שלו כבסיס החדש; אחרת, הרצף הנוכחי הואiפחות האינדקס שבראש המחסנית. שמור את הרצף הארוך ביותר שמדדת.
פתרון
שני דברים הופכים את זה לקשה יותר מאשר בדיקה של מחרוזת אחת. מקטעים תקינים מתחברים כשהם נוגעים זה בזה, ולכן () ו־(()) הסמוכים זה לזה נחשבים לרצף אחד באורך 6. ותו תועה אחד, כגון ) בתוך ())(()), חותך את המחרוזת, כך שאף תשובה לא יכולה לחצות אותו. בדיקת כל נקודת התחלה עולה O(n²). הפתרון הוא לזכור היכן התחיל הרצף הנוכחי: מחסנית של אינדקסים עם סמן בסיס בתחתית מאפשרת לעשות זאת במעבר אחד, ושני מעברים עם מונים פשוטים מאפשרים לעשות זאת בלי מחסנית בכלל.
הרחב תת־מחרוזת מכל נקודת התחלה
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
קוראים תת־מחרוזת משמאל לימין תוך מעקב אחר מאזן שמוסיף 1 עבור ( ומחסיר 1 עבור ). תת־המחרוזת תקינה בדיוק כאשר המאזן לעולם אינו יורד מתחת ל־0 ומסתיים ב־0. ערך נמוך מ־0 פירושו שהגיע ) כשאין סוגר פתוח לסגור.
לכן קובעים נקודת התחלה ומתקדמים ימינה, תוך עדכון המאזן תו אחד בכל פעם. בכל פעם שהוא חוזר ל־0, הקטע מנקודת ההתחלה ועד לכאן תקין, ומתעדים את אורכו. ברגע שהוא יורד מתחת ל־0, עוצרים: ה־) הזה נשאר ללא התאמה בכל קטע ארוך יותר שמתחיל בנקודה זו. לכל תת־מחרוזת תקינה יש נקודת התחלה כלשהי, ואתם בודקים כל נקודת סיום אפשרית עבורה, כך שלא מפספסים דבר.
הבעיה היא העלות. במחרוזת של 59998 תווים ( ואחריהם (), המאזן לעולם אינו יורד מתחת ל־0, ולכן מכל נקודת התחלה מתקדמים עד הסוף: בערך n²/2 = 1.8 × 10^9 צעדים עבור n = 6 × 10^4. הבדיקות הגדולות בנויות כך. (בדיקה של כל תת־מחרוזת מחדש במקום להרחיב אותה תהיה איטית עוד יותר, O(n³).)
אלגוריתם
- הגדר את
bestל־0. - עבור כל נקודת התחלה, הגדר את
balanceל־0 והתקדם עם נקודת הסיום מנקודת ההתחלה ועד התו האחרון. - הוסף 1 עבור
(והחסר 1 עבור). - אם
balanceקטן מ־0, עצור עבור נקודת התחלה זו. אם הוא 0, עדכן אתbestעם אורך הרצףend - start + 1. - החזר את
best.
def longestValidParentheses(s):
best = 0
for start in range(len(s)):
balance = 0
for end in range(start, len(s)):
balance += 1 if s[end] == "(" else -1
if balance < 0:
# A ')' without a partner: no longer run starts here
break
if balance == 0:
best = max(best, end - start + 1)
return bestמחסנית של אינדקסים עם סמן בסיס
האינטואיציה
התאמת סוגריים באמצעות מחסנית מוכרת: דוחפים כל (, ושולפים אחד עבור כל ). כאן צריך גם אורכים, ולכן דוחפים אינדקסים ושומרים בתחתית המחסנית אינדקס נוסף: בסיס, המיקום שממש לפני הרצף שבו נמצאים. בהתחלה לא נקרא דבר, לכן הבסיס הוא -1.
כשנתקלים ב־(, דוחפים את האינדקס שלו. כשנתקלים ב־), שולפים. שני דברים יכולים לקרות. אם המחסנית ריקה עכשיו, שלפת את הבסיס, ולכן ל־) הזה לא היה מה לסגור. שום תת־מחרוזת תקינה לא יכולה להכיל אותו, והוא הופך לבסיס החדש: דוחפים את האינדקס שלו. אחרת, האינדקס שנותר בראש המחסנית הוא התו האחרון שלפני הרצף שמסתיים ב־i: או ( שעדיין פתוח, או הבסיס. כל מה שאחריו ועד i מותאם, והרצף לא יכול להגיע רחוק יותר שמאלה, לכן אורכו הוא i - top.
הנה ())((()):
i = 0,(: דוחפים 0. המחסנית[-1, 0].i = 1,): שולפים 0. בראש המחסנית נמצא -1, לכן אורך הרצף הוא1 - (-1) = 2.i = 2,): שולפים את -1 והמחסנית ריקה. ל־)הזה אין סוגר תואם, לכן דוחפים את 2 כבסיס החדש. המחסנית[2].i = 3, 4, 5, שלושה תווי(: דוחפים אותם. המחסנית[2, 3, 4, 5].i = 6,): שולפים את 5. בראש המחסנית נמצא 4, לכן אורך הרצף הוא6 - 4 = 2.i = 7,): שולפים את 4. בראש המחסנית נמצא 3, לכן אורך הרצף הוא7 - 3 = 4, וזו התשובה.
הבסיס הוא מה שמאפשר לחלקים צמודים להתחבר. במקרה של ()(()), הזוג הראשון נמדד כ־1 - (-1) = 2, וה־) האחרון שולף את האינדקס 2 ומוצא שוב את -1 בראש המחסנית, לכן הוא נמדד כ־5 - (-1) = 6. מדידה החל מה־( התואם במקום זאת הייתה נותנת 4 ומפספסת את ה־() שלפניו. כל אינדקס נדחף ונשלף לכל היותר פעם אחת, לכן המעבר הוא O(n), והמחסנית יכולה להכיל עד n+1 אינדקסים.
אלגוריתם
- התחילו מחסנית שמכילה את -1 והגדירו את
bestל־0. - עבור כל אינדקס
i, דחפו אתiאםs[i]הוא(. - אם הוא
), הסירו איבר אחד מהמחסנית. - אם המחסנית ריקה כעת, דחפו את
iכבסיס החדש. אחרת, עדכנו אתbestבאמצעותi - top. - החזירו את
best.
def longestValidParentheses(s):
# The bottom of the stack is the index just before the current run
stack = [-1]
best = 0
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
stack.pop()
if not stack:
# This ')' has no partner: it becomes the new base
stack.append(i)
else:
best = max(best, i - stack[-1])
return bestסופרים פתיחות וסגירות בשני מעברים
האינטואיציה
המחסנית רק אומרת לך היכן התחילה המקטע הנוכחי. גם שני מונים יכולים לעשות זאת. עוברים משמאל לימין וסופרים את opens ואת closes מאז האיפוס האחרון. כשהם שווים, כל מה שמאז האיפוס תקין, ואורכו 2 × closes. כש-closes עולה על opens, ל-) אין בן זוג — בדיוק ברגע שבו המחסנית איבדה את הבסיס שלה — ולכן מאפסים את שני המונים ל-0.
מעבר אחד אינו מספיק. ( שלא נסגר משאיר את opens גדול יותר לתמיד, והספירות לעולם לא ישתוו שוב. במחרוזת (() המעבר משמאל לימין מסתיים עם 2 פתיחות וסגירה אחת, ולא מוצא דבר, אף ש-() מופיע שם. לכן עוברים פעם שנייה, מימין לשמאל, ומחליפים בין התפקידים: מאפסים כש-opens עולה על closes. בקריאה לאחור, (() נותן סגירה, ואז פתיחה (שוויון: אורך 2), ואז פתיחה שמביאה לאיפוס. התשובה היא הגדולה מבין שתי התוצאות.
מדוע שני מעברים תופסים כל מקטע: המקטע הארוך ביותר תחום בתווים שאי אפשר להתאים להם בן זוג, או בקצות המחרוזת. אם הגבול השמאלי שלו הוא ) מיותר או תחילת המחרוזת, המעבר משמאל לימין מאפס את המונים בדיוק במקום שבו המקטע מתחיל, ורואה שהם משתווים במקום שבו הוא מסתיים. אם הגבול השמאלי שלו הוא ( מיותר, הגבול הימני שלו לא יכול להיות ), כי ה-) הזה היה סוגר את ה-( המיותר, והמקטע היה ארוך יותר. לכן הגבול הימני הוא ( מיותר או סוף המחרוזת, והמעבר מימין לשמאל תופס את המקטע באותה דרך. כל מעבר קורא את המחרוזת פעם אחת ומשתמש בשני מספרים שלמים, ולכן זמן הריצה הוא O(n) והזיכרון הנוסף הוא O(1).
אלגוריתם
- הציבו את
bestעל 0, ואתopensואתclosesעל 0. - עברו משמאל לימין, וספרו כל תו. כשהספירות שוות, עדכנו את
bestבאמצעות2 × closes. כשהערך שלclosesגדול יותר, אפסו את שניהם. - אפסו את שני המונים, ואז עברו באותו אופן מימין לשמאל, אך אפסו כשהערך של
opensגדול יותר. - החזירו את
best.
def longestValidParentheses(s):
best = 0
# Left to right: more ')' than '(' ends every run that started earlier
opens = closes = 0
for ch in s:
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * closes)
elif closes > opens:
opens = closes = 0
# Right to left: catches the runs that an unmatched '(' hid from the first pass
opens = closes = 0
for ch in reversed(s):
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * opens)
elif opens > closes:
opens = closes = 0
return best
מלכודות ומקרי קצה
רוב התשובות השגויות סופרות את הזוגות התואמים במקומות הלא נכונים, או מאבדות את תחילת הרצף.
- ספירת זוגות תואמים לאורך כל המחרוזת. ב־
())((())יש 3 זוגות, אבל הם לא כולם צמודים, והתשובה היא 4, לא 6. - מדידת הרצף מהמיקום של
(התואם. ב־()(())התו)האחרון תואם לאינדקס 2, מה שמחזיר 4 ומפספס את()שלפניו. מדדו מהמיקום שנותר במחסנית אחרי ההוצאה. - התחלה עם מחסנית ריקה. ל־
)הראשון ב־())אין מול מה למדוד, ו־)לא תואם מוציא איבר ממחסנית ריקה. בסיס -1 פותר את שתי הבעיות. - הרצת המונים בכיוון אחד בלבד.
(()מחזיר 0 משמאל לימין, ו־())מחזיר 0 מימין לשמאל; התשובה היא 2 בשני המקרים. - איפוס המונים כשהם שווים. ספירות שוות פירושן שהרצף עדיין עשוי להתארך, כמו ב־
()(); אפסו רק כשאחד הצדדים מוביל. - ב־Lua וב־R המיקומים מתחילים ב־1, לכן ערך הבסיס הראשון הוא 0, לא -1.
שאלות נפוצות3
מהי סיבוכיות הזמן של Longest Valid Parentheses?
גם פתרון המחסנית וגם פתרון המונים בשני מעברים קוראים כל תו מספר קבוע של פעמים, ולכן זמן הריצה שלהם הוא O(n). במקרה הגרוע, המחסנית זקוקה לזיכרון של O(n), למשל עבור מחרוזת שמכילה רק (, בעוד שהמונים זקוקים לזיכרון של O(1). ניסיון של כל נקודת התחלה הוא O(n²).
למה המחסנית מתחילה ב־-1?
אורך הרצף הוא האינדקס הנוכחי פחות האינדקס שממש לפני הרצף. ברצף שמתחיל באינדקס 0, האינדקס הקודם הוא -1, צעד אחד לפני המחרוזת. דחיפת -1 ראשון פירושה שהמחסנית לעולם אינה ריקה כשסוגר תואם ) מודד, וכשסוגר לא תואם ) מוציא אותו מהמחסנית, אותו ) הופך לבסיס החדש.
האם יש פתרון באמצעות תכנות דינמי לבעיה של הסוגריים התקינים הארוכים ביותר?
כן. נגדיר את end[i] כאורך תת־המחרוזת התקינה הארוכה ביותר שמסתיימת באינדקס i; ערכו הוא 0 כאשר s[i] הוא (. אם s[i-1] הוא (, אז end[i] = end[i-2] + 2. אם הוא ), נבדוק את j = i - end[i-1] - 1, התו שלפני הרצף שמסתיים ב־i-1: כאשר s[j] הוא (, הוא עוטף את הרצף הזה, ו־end[i] = end[i-1] + 2 + end[j-1], כאשר האיבר האחרון מחבר רצף שנוגע בו משמאל. התשובה היא הערך הגדול ביותר של end[i], בזמן ובזיכרון O(n).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def longestValidParentheses(s):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
s = "()(())"
הפלט הצפוי
6