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*. تكون خلية النجمة صحيحة إذا كانت الخلية التي تبعد عمودين إلى يسارها صحيحة، أو إذا كان عنصرها يطابق الحرف وكانت الخلية التي فوقها مباشرةً صحيحة.
الحل
يمكن أن تأخذ النجمة أي عدد من النسخ، ويعتمد العدد المناسب على ما يليها. تعامل مع الحرف ونجمةِه كوحدة واحدة لها حركتان: تخطَّها، أو استهلك حرفًا واحدًا وابقَ عندها. يجرّب جدولٌ يبيّن أي بادئات s تطابق أي بادئات p كلَّ اختيار مرة واحدة.
المطابقة من اليسار باستخدام الاستدعاء الذاتي
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
قارن اللواحق: يوضح match(i, j) ما إذا كان s[i:] يطابق p[j:]. يجب أن يطابق حرف أو نقطة من دون نجمة s[i]، ويجب أن يطابق الباقي بقية النمط. أما الوحدة x* فإما أن تأخذ صفرًا من النسخ ويتم تخطيها، أو تستهلك s[i] وتبقى على الوحدة نفسها، وهذا ما يسمح لنجمة واحدة بمطابقة أي عدد من الأحرف. يغطي الفرعان كل خيار تتيحه النجمة، لذا لا يفوتنا أي تطابق.
تقسم كل نجمة البحث إلى قسمين. مع 30 حرفًا a وعشر نسخ من a* يتبعها حرف b، تجرّب الاستدعاءات العودية نحو 8.5 × 10^8 طريقة لتوزيع الأحرف بين النجوم قبل أن تعطي الإجابة false، مع أن عدد الأزواج المختلفة (i, j) لا يتجاوز (n+1) × (m+1).
الخوارزمية
- اكتب
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] صحيحة. في الصف 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.* صحيحًا عند s باستخدام صفر من النسخ، ثم عند sk وsky بخطوة واحدة إلى أعلى في كل مرة.
تقرأ كل خانة الصف الذي فوقها أو الخانات الواقعة إلى يسارها، لذا فإن ملأ الجدول صفًا بعد صف يجعل هذه الخانات جاهزة.
الخوارزمية
- أنشئ جدولًا
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]. ينخفض استهلاك الذاكرة من نحو 10^6 خلية إلى صفّين، في كل منهما 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].
لماذا لا تستخدم مكتبة التعبيرات النمطية الخاصة باللغة؟
يريد المُحاوِر الخوارزمية، لا استدعاء مكتبة. كما أن العديد من محركات التعبيرات النمطية تُطابق باستخدام التراجع، وهو الاستدعاء التكراري البطيء في النهج الأول، لذا فإن عشر نسخ من a* تتبعها b عند مطابقتها مع سلسلة طويلة من أحرف a قد تجعلها تعمل لدقائق. ينتهي الجدول دائمًا في O(n × m).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def isMatch(s, p):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
s = "moon" p = "mo*n"
الإخراج المتوقع
true