Regular Expression Matching

Q: מהי סיבוכיות הזמן של התאמת ביטויים רגולריים?

פתרון הטבלה פועל בזמן O(n × m) , כאשר n הוא האורך של s ו- m הוא האורך של p , משום שכל תא קורא לכל היותר שני תאים אחרים. הוא דורש זיכרון של O(n × m) עבור הטבלה המלאה, או O(m) עם שתי שורות. רקורסיה רגילה יכולה להימשך זמן אקספוננציאלי עבור תבניות עם כוכביות רבות.

Q: למה תא כוכב קורא את התא שמעליו ולא את התא האלכסוני?

התא שמעל, dp[i-1][j] , מציג את אותה תבנית עם אות אחת פחות של s , והכוכבית עדיין נמצאת בו. לכן אחרי שהכוכבית בולעת את s[i-1] , היא יכולה לבלוע גם את s[i-2] , וכך הלאה במעלה העמודה. התא האלכסוני dp[i-1][j-2] מסיר את הכוכבית אחרי אות אחת, וכך מאפשר בדיוק עותק אחד במקום מספר כלשהו.

Q: במה זה שונה מהתאמה באמצעות תו כללי?

בהתאמת תווים כלליים, כמו בתבניות של שמות קבצים, * עומד בפני עצמו ומתאים לכל רצף של תווים, ו- ? מתאים לתו אחד. כאן * חוזר רק על הרכיב שלפניו, ותבנית התאמת כל טקסט היא .* . את שניהם פותרים באמצעות טבלה של קידומות, אבל מעבר הכוכבית שונה: התאמת תווים כלליים קוראת את dp[i][j-1] או את dp[i-1][j] .

קשהתכנון דינמי רקורסיה

+10

מקבלים מחרוזת s ותבנית p. בתבנית, אות מתאימה לאותה אות, נקודה . מתאימה לכל אות אחת, וכוכבית * פירושה אפס או יותר עותקים של הרכיב שמופיע ממש לפניה, שהוא אות או נקודה. יש להחזיר true אם התבנית מתאימה לכל s, ולא רק לחלק ממנה, ו-false אחרת.

פונקציה

isMatch(s: string, p: string) → boolean

sstring: המחרוזת להתאמה, אותיות קטנות בלבד
pstring: התבנית של אותיות, נקודות וכוכבים
מחזירהboolean: true אם p תואם לכל s, false אחרת

אילוצים

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s מכילה רק אותיות אנגליות קטנות.
p מכיל רק אותיות אנגליות קטנות, . ו־*.
כל * מופיע אחרי אות או ., ולכן p לעולם לא מתחיל ב־* ולעולם אין בו שתי כוכביות ברצף.

דוגמאות

קלט: s = "moon"p = "mo*n"
פלט: true
הסבר: o* לוקח את שתי האותיות o, ולכן m, o* ו־n מאייתים בדיוק את moon.

קלט: s = "tree"p = "t.e"
פלט: false
הסבר: t.e מתאים רק למחרוזות בנות שלוש אותיות: t, כל אות שהיא, ואז e. הוא מתאים ל־tre בתחילת tree, אבל ה־e האחרונה נשארת, והתאמה חייבת לכסות את כל s.

קלט: s = "sky"p = "z*s.*y"
פלט: true
הסבר: z* לוקח אפס עותקים של z, ‏s מתאים ל־s, ‏.* לוקח את k, ו־y מתאים ל־y. אות עם כוכבית יכולה לייצג כלום, ולכן z שלא מופיעה ב־sky לא עולה כלום.

+29 בדיקות נסתרות בשליחה

שאלת המשך

האם אפשר לתמוך גם ב־+, שפירושו עותק אחד או יותר של הרכיב שלפניו, באמצעות אותה הטבלה?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

כוכבית יכולה להתאים לכל מספר של עותקים, והמספר הנכון תלוי במה שבא אחריה. התאמה של כמה שיותר תווים נכשלת: מול aaa, התבנית a*a מאפשרת ל־a* לבלוע את כל שלוש האותיות ולא משאירה דבר ל־a האחרונה. הרעיון שפותר את הבעיה הוא להתייחס לאות ולכוכבית שלה כאל יחידה אחת עם שתי אפשרויות: לדלג עליה, או לתת לה לבלוע אות אחת ולהישאר במקומה. טבלה מתעדת אם כל קידומת של s תואמת לכל קידומת של p, כך שכל אפשרות נבדקת פעם אחת, ושתי שורות שלה מספיקות.

התאמה משמאל באמצעות רקורסיה

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

האינטואיציה

נגדיר את match(i, j) כך שתקבע אם הסיומת s[i:] תואמת לסיומת p[j:]. אם התבנית מוצתה, היא תואמת רק אם גם המחרוזת מוצתה. אחרת, נחשב את first: יש אות s[i], ו-p[j] היא אותה אות או נקודה.

כעת נבחן תו אחד קדימה. אם p[j+1] הוא כוכבית, p[j]* היא יחידה אחת עם שתי אפשרויות. אפשר לקחת אפס עותקים: לדלג על שני התווים באמצעות match(i, j+2). או, אם first מתקיים, אפשר לקחת עותק אחד: לצרוך את s[i] ולהישאר באותה יחידה באמצעות match(i+1, j), מוכנים לקחת עותק נוסף. ההישארות ב-j היא שמאפשרת לכוכבית אחת לקחת כל מספר של אותיות, אחת בכל פעם. בלי כוכבית, p[j] חייב להתאים בדיוק לאות אחת: first and match(i+1, j+1).

הפעולה איטית כי כל כוכבית מפצלת את החיפוש לשניים, וכישלון מתגלה לעיתים קרובות רק ממש בסוף. נבחן 30 אותיות a מול עשרה עותקים של a* ולאחריהם b. הרקורסיה מנסה כל דרך לחלק חלק מ-30 אותיות ה-a או את כולן בין עשר הכוכביות, בערך 8.5 × 10^8 דרכים, ומבצעת בערך 2 × 10^9 קריאות לפני שהיא יכולה להשיב false. בבדיקות הגדולות יש 1000 אותיות. ובכל זאת, יש רק (n+1) × (m+1) זוגות שונים (i, j).

אלגוריתם

כתבו match(i, j) עבור הסיומות שמתחילות ב־i וב־j.
אם j נמצא אחרי סוף p, החזירו האם i נמצא אחרי סוף s.
הגדירו את first לפי השאלה אם s[i] קיים ואם p[j] הוא s[i] או נקודה.
אם p[j+1] הוא כוכבית, החזירו את match(i, j+2) או את first and match(i+1, j).
אחרת, החזירו את first and match(i+1, j+1). התשובה היא match(0, 0).

def isMatch(s, p):
    n, m = len(s), len(p)

    def match(i, j):
        # Does s[i:] match p[j:]?
        if j == m:
            return i == n
        first = i < n and p[j] in (s[i], ".")
        if j + 1 < m and p[j + 1] == "*":
            # use p[j] zero times, or let it eat s[i] and stay on the same x*
            return match(i, j + 2) or (first and match(i + 1, j))
        return first and match(i + 1, j + 1)

    return match(0, 0)

מלא טבלת תחיליות

האינטואיציה

מצב. נניח ש-dp[i][j] מציין אם i האותיות הראשונות של s תואמות ל-j התווים הראשונים של p. האינדקס 0 מציין קידומת ריקה.

שורת הבסיס ועמודת הבסיס. dp[0][0] הוא true: תבנית ריקה תואמת למחרוזת ריקה. עמודה 0 היא false מתחתיו, כי תבנית ריקה לא יכולה להתאים לאות. שורה 0 היא המקרה העדין: קידומת של תבנית תואמת למחרוזת הריקה רק אם כל איבר בה מסומן בכוכבית, כמו z* או a*b*. לכן dp[0][j] הוא true כאשר p[j-1] הוא כוכבית ו-dp[0][j-2] הוא true.

מעברים. אם p[j-1] הוא אות או נקודה, הוא חייב להתאים לאות האחרונה s[i-1], וגם שאר התווים חייבים להתאים: dp[i-1][j-1], התא האלכסוני. אם p[j-1] הוא כוכבית, האיבר שלה הוא x = p[j-2], ולכוכבית יש שתי אפשרויות. אפס עותקים: מסירים את x* מהתבנית, dp[i][j-2], שני תאים שמאלה. עותק אחד נוסף: אם x תואם ל-s[i-1], האות הזאת היא אחד העותקים, ואותו x* עדיין צריך להתאים למחרוזת הקצרה יותר, לכן קוראים את dp[i-1][j], התא שממש מעליו באותה עמודה. כל עותק הוא צעד אחד למעלה באותה עמודה, וכך כוכבית יחידה מכסה כל מספר של אותיות.

הנה הטבלה עבור sky ו-z*s.*y, עם עמודות עבור הקידומות "", z, z*, z*s, z*s., z*s.*, z*s.*y (T הוא true, F הוא false). השורה "" היא [T, F, T, F, F, F, F]: רק z* יכולה להיות ריקה. השורה s היא [F, F, F, T, F, T, F]: s תואמת ל-s, כאשר z* שמעליה ריקה באלכסון, ואז .* לוקח אפס עותקים. השורה sk היא [F, F, F, F, T, T, F]: התא של z*s.* מקבל את ערך ה-true שלו מעותק אחד נוסף, כשהנקודה תופסת את k, מתוך ה-T שממש מעליו. השורה sky היא [F, F, F, F, F, T, T]: הכוכבית של הנקודה תופסת את y באותו אופן, צעד שני למעלה באותה עמודה, ואז y תואמת ל-y באלכסון. התא האחרון הוא true.

כל תא קורא מהשורה שמעליו או מתאים שמשמאלו, לכן מילוי שורה אחר שורה, משמאל לימין, מבטיח שהם יהיו מוכנים. מדובר ב-(n+1) × (m+1) תאים, בערך 10^6 בבדיקות הגדולות ביותר, עם עבודה קבועה לכל תא.

אלגוריתם

צרו טבלה dp של (n+1) × (m+1) ערכי false והגדירו את dp[0][0] כ־true.
עבור j מ־2 עד m, הגדירו את dp[0][j] כ־true כאשר p[j-1] הוא כוכבית ו־dp[0][j-2] הוא true.
עבור כל תא שבו i ≥ 1 ו־j ≥ 1, אם p[j-1] הוא כוכבית, הגדירו אותו ל־dp[i][j-2] או (p[j-2] תואם ל־s[i-1] ו־dp[i-1][j]).
אחרת הגדירו אותו ל־(p[j-1] תואם ל־s[i-1]) וגם dp[i-1][j-1].
החזירו את dp[n][m].

def isMatch(s, p):
    n, m = len(s), len(p)
    # dp[i][j]: do the first i letters of s match the first j characters of p?
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True  # an empty pattern matches an empty string
    for j in range(2, m + 1):
        # an empty string matches only patterns like x*y*z*
        dp[0][j] = p[j - 1] == "*" and dp[0][j - 2]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = dp[i][j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and dp[i - 1][j]  # one more copy eats s[i-1]
                dp[i][j] = zero or more
            else:
                dp[i][j] = p[j - 1] in (s[i - 1], ".") and dp[i - 1][j - 1]
    return dp[n][m]

השאר רק שתי שורות

האינטואיציה

שורה i קוראת שני תאים משורה i-1, את התא האלכסוני ואת התא שמעליו, ותא אחד משלה, שני מקומות שמאלה. שורות שמעליה לעולם אינן נקראות שוב. שמור שני מערכים: prev עבור השורה שהושלמה ו-cur עבור השורה שאתה ממלא, והחלף ביניהם אחרי כל אות של s. המעברים נשארים זהים: אפס עותקים הוא cur[j-2], עותק נוסף אחד הוא prev[j], התאמה רגילה היא prev[j-1].

התחל עם prev כשורת הבסיס עבור המחרוזת הריקה. הגדר את cur[0] ל-false בתחילת כל שורה: אחרי החלפה, cur מכיל שורה ישנה, והערך הראשון בשורת הבסיס הוא true.

בכל שורה יש m + 1 ערכים, כך שהזיכרון מצטמצם מכמיליון תאים לשתי שורות של 1001. בניגוד למרחק עריכה, אי אפשר להחליף בין שתי הקלטים כדי לקצר את השורות, כי המחרוזת והתבנית ממלאות תפקידים שונים.

אלגוריתם

מלאו את prev בשורת הבסיס: true במיקום 0, ובמיקום j כאשר p[j-1] הוא כוכבית ו-prev[j-2] הוא true.
עבור כל אות ב-s, הגדירו את cur[0] ל-false.
מלאו את cur[1..m]: תא של כוכבית הוא cur[j-2] או (התו תואם ו-prev[j]); כל תא אחר הוא (התו תואם) ו-prev[j-1].
החליפו בין prev ל-cur.
החזירו את prev[m].

def isMatch(s, p):
    n, m = len(s), len(p)
    # prev[j]: do the letters of s before the current one match the first j characters of p?
    prev = [False] * (m + 1)
    prev[0] = True  # row 0: the empty string
    for j in range(2, m + 1):
        prev[j] = p[j - 1] == "*" and prev[j - 2]  # only patterns like x*y*z* match it
    for i in range(1, n + 1):
        cur = [False] * (m + 1)  # cur[0] stays False: an empty pattern matches no letters
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = cur[j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and prev[j]  # one more copy eats s[i-1]
                cur[j] = zero or more
            else:
                cur[j] = p[j - 1] in (s[i - 1], ".") and prev[j - 1]
        prev = cur
    return prev[m]

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

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

נותנים לכוכבית לקחת כמה שיותר אותיות. a*a מול aaa היא התאמה, אבל a* חמדנית בולעת את כל שלוש האותיות, וה־a האחרונה נכשלת.
קוראים את dp[i-1][j-2] כדי לקבל עותק אחד נוסף. כך הכוכבית יכולה לקחת לכל היותר אות אחת, ולכן aa מול a* מחזיר false. הישארו בעמודה של הכוכבית: dp[i-1][j].
משאירים את שורה 0 כולה false, למעט התא הראשון. אז b מול a*b נכשל, כי ה־b צריך ש־a* יתאים לקידומת הריקה שלפניו.
משווים את s[i-1] לכוכבית עצמה במקום לאיבר שלה, p[j-2].
מתייחסים אל * כאל "כל טקסט", כמו בדפוסי שמות קבצים. כאן היא חוזרת רק על האיבר שלפניה; כל טקסט הוא .*.
מקבלים התאמה חלקית. t.e מתאים לתחילת tree, אבל התשובה היא false כי נשארת אות.
שוכחים את cur[0] = false בגרסה עם שתי שורות. אחרי ההחלפה הראשונה, cur[0] מכיל את הערך true של שורת הבסיס.

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

מהי סיבוכיות הזמן של התאמת ביטויים רגולריים?

פתרון הטבלה פועל בזמן O(n × m), כאשר n הוא האורך של s ו-m הוא האורך של p, משום שכל תא קורא לכל היותר שני תאים אחרים. הוא דורש זיכרון של O(n × m) עבור הטבלה המלאה, או O(m) עם שתי שורות. רקורסיה רגילה יכולה להימשך זמן אקספוננציאלי עבור תבניות עם כוכביות רבות.

למה תא כוכב קורא את התא שמעליו ולא את התא האלכסוני?

התא שמעל, dp[i-1][j], מציג את אותה תבנית עם אות אחת פחות של s, והכוכבית עדיין נמצאת בו. לכן אחרי שהכוכבית בולעת את s[i-1], היא יכולה לבלוע גם את s[i-2], וכך הלאה במעלה העמודה. התא האלכסוני dp[i-1][j-2] מסיר את הכוכבית אחרי אות אחת, וכך מאפשר בדיוק עותק אחד במקום מספר כלשהו.

במה זה שונה מהתאמה באמצעות תו כללי?

בהתאמת תווים כלליים, כמו בתבניות של שמות קבצים, * עומד בפני עצמו ומתאים לכל רצף של תווים, ו-? מתאים לתו אחד. כאן * חוזר רק על הרכיב שלפניו, ותבנית התאמת כל טקסט היא .*. את שניהם פותרים באמצעות טבלה של קידומות, אבל מעבר הכוכבית שונה: התאמת תווים כלליים קוראת את dp[i][j-1] או את dp[i-1][j].

למה לא להשתמש בספריית הביטויים הרגולריים של השפה?

המראיין רוצה לראות את האלגוריתם, לא קריאה לספרייה. יש גם סיכון ממשי: מנועי ביטויים רגולריים רבים מבצעים התאמה באמצעות חזרה לאחור, שהיא הרקורסיה האיטית של הגישה הראשונה. תבנית כמו עשר עותקים של a* ואחריהם b, מול רצף ארוך של האות a, עלולה לגרום למנוע כזה לפעול במשך דקות. הטבלה תמיד מסיימת בזמן O(n × m).

Python

def isMatch(s, p):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s = "moon"
p = "mo*n"

צפוי

true

Regular Expression Matching

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

התאמה משמאל באמצעות רקורסיה

מלא טבלת תחיליות

השאר רק שתי שורות

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

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

בעיות דומות