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: صحيح إذا كان p يطابق s بالكامل، وخطأ خلاف ذلك

القيود

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. تحاول الاستدعاءات العودية كل طريقة لتوزيع بعض أحرف 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 من القيم 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].

ابدأ باستخدام prev بوصفه الصف الأساسي للسلسلة الفارغة. عيّن cur[0] إلى false في بداية كل صف: بعد التبديل، يحتوي cur على صف قديم، وتكون الخانة الأولى في الصف الأساسي true.

يحتوي كل صف على m + 1 خانة، لذا تنخفض الذاكرة من نحو 10^6 خلية إلى صفين من 1001 خانة. وعلى عكس مسافة التحرير، لا يمكنك تبديل المدخلين لجعل الصفوف أقصر، لأن السلسلة والنمط يؤديان دورين مختلفين.

الخوارزمية

املأ prev بالصف الأساسي: تكون القيمة true عند 0، وعند j إذا كان p[j-1] نجمة وكانت prev[j-2] true.
لكل حرف من s، عيّن cur[0] إلى false.
املأ cur[1..m]: تكون قيمة الخلية التي تحتوي على نجمة هي cur[j-2] أو (إذا طابق العنصر وكانت prev[j] true)؛ وأي خلية أخرى تكون (إذا تطابق العنصر) وكانت prev[j-1] true.
بدّل 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

مسائل مشابهة