Regular Expression Matching
נתונה לך מחרוזת s ותבנית p. בתבנית, אות תואמת לאותה אות, נקודה . תואמת לכל אות אחת, וכוכבית * פירושה אפס או יותר עותקים של הרכיב שלפניה, שהוא אות או נקודה. החזר true אם התבנית תואמת לכל s, ו־false אחרת.
פונקציה
- sstring
- המחרוזת שיש להתאים, אותיות קטנות בלבד
- pstring
- התבנית של אותיות, נקודות וכוכבים
- מחזירהboolean
- אמת אם p תואם לכל s, אחרת שקר
אילוצים
1 ≤ s.length ≤ 10001 ≤ p.length ≤ 1000sמכילה רק אותיות אנגליות קטנות.pמכיל רק אותיות אנגליות קטנות,.ו-*.- כל
*מופיע אחרי אות או אחרי., לכןpאף פעם לא מתחיל ב־*ואף פעם אין שתי כוכביות ברצף.
דוגמאות
- קלט
- s = "moon"p = "mo*n"
- פלט
- true
- הסבר
o*לוקח את שתי האותיות o, כך ש-m,o*ו-n מאייתים בדיוק אתmoon.
- קלט
- s = "tree"p = "t.e"
- פלט
- false
- הסבר
t.eמתאים ל־tre, תחילתtree, אבל ה־e האחרונה נשארת ללא התאמה, והתאמה חייבת לכסות את כלs.
- קלט
- s = "sky"p = "z*s.*y"
- פלט
- true
- הסבר
z*לוקח אפס עותקים של z, s מתאים ל־s, .*לוקח את k, ו־y מתאים ל־y.
שאלת המשך
האם תוכל לתמוך גם ב־+, שמציין עותק אחד או יותר של האלמנט שלפניו, באמצעות אותה טבלה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
התייחסו לאות ואחריה
*כאל יחידה אחת. כשמשווים את היחידה הזו לאות הבאה ב־s, מהם שני הדברים שהיא יכולה לעשות?היחידה יכולה לא להתאים לשום דבר ולדלג, או להתאים לאות אחת ולהישאר במקומה, מוכנה לקבל עוד. כל תו אחר בתבנית חייב להתאים לאות אחת בדיוק. ניסיון של שני המהלכים בכל כוכבית חוזר על הרבה עבודה.
שמרו בטבלה אם כל קידומת של
sתואמת לכל קידומת שלp. מלאו תחילה את השורה עבור המחרוזת הריקה, שבה רק תבניות כמוa*b*תואמות. תא של כוכבית הוא true אם התא שנמצא שתי עמודות משמאלו הוא true, או אם הרכיב שלו תואם לאות והתא שמעליו הוא true.
פתרון
כוכבית יכולה לקבל כל מספר של עותקים, והמספר הנכון תלוי במה שבא אחריה. התייחס לאות ולכוכבית שלה כאל יחידה אחת עם שתי אפשרויות: לדלג עליה, או לצרוך אות אחת ולהישאר עליה. טבלה שלפיה קידומות של s מתאימות לקידומות של p מנסה כל אפשרות פעם אחת.
התאמה משמאל באמצעות רקורסיה
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
משווים סיומות: match(i, j) מציינת אם s[i:] תואמת ל־p[j:]. אות או נקודה ללא כוכבית חייבת להתאים ל־s[i], והשאר חייב להתאים. יחידה x* או לוקחת אפס עותקים ומדלגים עליה, או צורכת את s[i] ונשארת באותה יחידה; כך כוכבית אחת יכולה להתאים לכל מספר של אותיות. שני הענפים מכסים את כל האפשרויות של כוכבית, ולכן אף התאמה לא מתפספסת.
כל כוכבית מפצלת את החיפוש לשניים. עבור 30 אותיות a מול עשרה עותקים של a* ולאחריהם b, הרקורסיה מנסה כ־8.5 × 10^8 דרכים לחלק את האותיות בין הכוכביות לפני שהיא מחזירה false, ובכל זאת יש רק (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. dp[0][0] הוא true. בשורה 0, המחרוזת הריקה תואמת לתחילית של תבנית רק אם כל אחד מהאיברים בה מסומן בכוכבית, כמו z* או a*b*.
אות או נקודה ב-p[j-1] חייבת להתאים ל-s[i-1], ושאר המחרוזת חייב להתאים: האלכסון, dp[i-1][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*s.* היא true עבור s באמצעות אפס עותקים, ואז עבור sk ועבור sky צעד אחד למעלה בכל פעם.
כל תא קורא את השורה שמעליו או תאים שמשמאלו, ולכן מילוי שורה אחר שורה מבטיח שהם כבר מוכנים.
אלגוריתם
- צור טבלה
dpשל ערכי false בגודל(n+1) × (m+1)והגדר את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]. הזיכרון מצטמצם מכמיליון תאים לשתי שורות של 1001 תאים. אי אפשר להחליף בין הקלטים כדי לקצר את השורות, כי למחרוזת ולתבנית יש תפקידים שונים.
אלגוריתם
- מלא את
prevבשורה 0 של הטבלה. - עבור כל אות ב־
s, הגדר אתcur[0]לערך false ומלא אתcur[1..m]לפי כללי הטבלה, תוך קריאה מתוךprevעבור השורה שמעל. - החלף בין
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. - להשאיר את שורה 0 כולה false אחרי התא הראשון שלה. אז
bמולa*bנכשל, כי ה־b זקוקה לכך ש־a*יתאים לקידומת הריקה. - להשוות את
s[i-1]לכוכבית במקום לאיבר שלהp[j-2]. אזaמולa*נכשל. - לא לאפס את
cur[0]ל־false בגרסה עם שתי השורות. אחרי החלפה, הוא עלול להכיל את הערך true של שורת הבסיס, ואזaabמולbמחזיר true.
שאלות נפוצות3
מהי סיבוכיות הזמן של התאמת ביטויים רגולריים?
פתרון הטבלה רץ בזמן O(n × m) עבור מחרוזת באורך n ודפוס באורך m, כי כל תא קורא לכל היותר שני תאים אחרים. הוא דורש O(n × m) זיכרון עבור הטבלה המלאה, או O(m) עם שתי שורות. רקורסיה פשוטה יכולה לדרוש זמן מעריכי עבור דפוסים עם כוכביות רבות.
במה זה שונה מהתאמה באמצעות תו כללי?
בהתאמת תווים כלליים, כמו בדפוסי שמות קבצים, * עומד בפני עצמו ומתאים לכל רצף של תווים, ו־? מתאים לתו אחד. כאן * חוזר רק על הרכיב שלפניו, וכל טקסט הוא .*. בשניהם משתמשים בטבלה על פני קידומות, אבל כוכבית התווים הכלליים קוראת את dp[i][j-1] או את dp[i-1][j].
למה לא להשתמש בספריית הביטויים הרגולריים של השפה?
המראיין רוצה את האלגוריתם, לא קריאה לספרייה. מנועי regex רבים מבצעים התאמה גם באמצעות חזרה לאחור, הרקורסיה האיטית של הגישה הראשונה, ולכן עשר חזרות על a* ואחריהן b מול רצף ארוך של האות a יכולות לגרום להם לפעול במשך דקות. הטבלה תמיד מסתיימת בזמן O(n × m).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def isMatch(s, p):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
s = "moon" p = "mo*n"
הפלט הצפוי
true