Valid Parentheses

Q: מהי סיבוכיות הזמן של Valid Parentheses?

פתרון המחסנית רץ בזמן O(n) , מכיוון שכל תו נדחף או נשלף לכל היותר פעם אחת. במקרה הגרוע הוא משתמש במקום O(n) , עבור מחרוזת שמכילה רק תווים פותחים. הסרה חוזרת ונשנית של זוגות תואמים אורכת זמן O(n²) , מכיוון שמחרוזת מקוננת עמוק מאבדת רק זוג אחד בכל סבב.

קלמחסנית

+10

ניתנת לך מחרוזת s המורכבת רק מתווי הסוגריים (, ), [, ], { ו-}. החזר true כאשר הסוגריים מאוזנים: כל סוגר סוגר את הסוגר הפתוח האחרון, השניים מאותו סוג, ולא נשארים סוגריים פתוחים בסוף. אחרת, החזר false.

פונקציה

isValid(s: string) → boolean

sstring: מחרוזת הסוגריים לבדיקה
מחזירהboolean: האם הסוגריים מאוזנים

אילוצים

1 ≤ s.length ≤ 10⁴
s מכילה רק את התווים (, ), [, ], { ו-}.

דוגמאות

קלט: s = "[]{}()"
פלט: true
הסבר: שלושה זוגות עומדים זה לצד זה, וכל אחד מהם נסגר מיד לאחר שנפתח.

קלט: s = "{(})"
פלט: false
הסבר: הסוגר } מופיע בזמן שהסוגר ( שנפתח אחריו עדיין פתוח, ולכן הוא סוגר סוג לא נכון של סוגריים.

שאלת המשך

אם המחרוזת הכילה רק סוגריים עגולים, האם היית יכול לבדוק אותה באמצעות מונה יחיד במקום מחסנית, ובזיכרון נוסף של O(1)?

פתרון

ספירת הסוגריים אינה מספיקה: {(}) יש סוגר פותח וסוגר סוגר אחד מכל סוג, ובכל זאת היא שגויה, כי הסדר חשוב. מחסנית שומרת את הסוגריים שעדיין פתוחים לפי סדר פתיחתם, ולכן מעבר אחד בעזרת מחסנית מספיק כדי לקבוע אם המחרוזת כולה תקינה.

הסירי שוב ושוב זוגות תואמים

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

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

בכל סבב סורקים את כל המחרוזת ובונים עותק חדש, ומחרוזת מקוננת כמו (((...))) מאבדת זוג אחד בכל סבב. נדרשים עד n/2 סבבים של עבודה O(n), ובסך הכול O(n²).

אלגוריתם

מחקו את כל המופעים של (), [] ו־{} מהמחרוזת.
אם בסבב הזה לא נמחק דבר, עצרו.
אחרת, חזרו על הפעולה עם המחרוזת הקצרה יותר.
החזירו true אם המחרוזת התרוקנה, ו־false אם נותרו בה סוגריים כלשהם.

def isValid(s):
    while True:
        # Delete every adjacent matched pair in one round.
        shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
        if shorter == s:
            break  # nothing left to delete
        s = shorter
    return s == ""

מעבר אחד עם מחסנית

האינטואיציה

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

דחוף למחסנית את הסוגר הסוגר שכל סוגר פותח מצפה לו. לאחר מכן, הסוגר הסוגר חייב להיות זהה לראש המחסנית. מחסנית ריקה פירושה שאין לה מה לסגור; ראש שונה פירושו שהוא סוגר סוג לא נכון, כפי שקורה עם } בתוך {(}) כאשר ) נמצא בראש. בסוף, כל מה שנותר במחסנית, כמו ב-((, נפתח ולא נסגר מעולם. כל תו נדחף או נשלף פעם אחת: זמן O(n), ולכל היותר n איברים במחסנית.

אלגוריתם

צור מחסנית ריקה.
עבור סוגר פותח, דחוף אליה את הסוגר הסוגר התואם.
עבור סוגר סוגר, החזר false אם המחסנית ריקה או אם התו שבראשה שונה; אחרת, בצע שליפה.
אחרי התו האחרון, החזר true רק אם המחסנית ריקה.

def isValid(s):
    closers = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for ch in s:
        if ch in closers:
            stack.append(closers[ch])
        elif not stack or stack.pop() != ch:
            return False
    return not stack

מלכודות ומקרי קצה

ספירת כל סוג של סוגריים. ל־{(}) יש מספרים תואמים, והוא עדיין לא תקין, ו־)( נכשל רק בגלל הסדר.
הוצאה ממחסנית ריקה. מחרוזת שמתחילה בסוגר סוגר, כגון } או )]}, חייבת להחזיר false במקום לגרום לקריסה.
דילוג על הבדיקה הסופית. (([{ אף פעם לא נתקל בסוגר סוגר שגוי, ולכן רק האיברים שנותרו במחסנית מראים שהוא לא תקין.
הסתמכות על האורך. אורך אי־זוגי תמיד מעיד על קלט לא תקין, אבל אורך זוגי לא מוכיח דבר: גם (] וגם ())( אינם תקינים.
בגישת ההסרה, העברת סוגריים לביטוי רגולרי או לתבנית Lua בלי לבצע להם escaping. ל־( ול־[ יש שם משמעות; השתמשו בהחלפה של טקסט רגיל.

שאלות נפוצות3

מהי סיבוכיות הזמן של Valid Parentheses?

פתרון המחסנית רץ בזמן O(n), מכיוון שכל תו נדחף או נשלף לכל היותר פעם אחת. במקרה הגרוע הוא משתמש במקום O(n), עבור מחרוזת שמכילה רק תווים פותחים. הסרה חוזרת ונשנית של זוגות תואמים אורכת זמן O(n²), מכיוון שמחרוזת מקוננת עמוק מאבדת רק זוג אחד בכל סבב.

למה משתמשים במחסנית עבור סוגריים תקינים?

סוגריים מקוננים זה בתוך זה, ולכן הסוגר שנפתח אחרון חייב להיסגר ראשון. מחסנית שומרת את הסוגר הזה בראש, כך שאפשר לקרוא אותו ולהסיר אותו בזמן קבוע, וכך כל הבדיקה נשארת ב־O(n).

האם מחרוזת ריקה נחשבת לסוגריים תקינים?

כן. במחרוזת ריקה אין סוגר לא תואם, ולכן היא מאוזנת: המחסנית נשארת ריקה, וללולאת ההסרה אין מה להסיר. בבעיה הזו, ב־s יש תמיד לפחות תו אחד.

def isValid(s):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

s = "[]{}()"

הפלט הצפוי

true