ما هي Regular Expression Matching؟ شرح Regex باستخدام Dynamic Programming

في النسخة الخوارزمية الكلاسيكية من Regular Expression Matching نملك String وPattern، ويدعم Pattern عاملين خاصين:

.  → أي حرف واحد
*  → صفر أو أكثر من العنصر السابق

مثلاً:

String: aa
Pattern: a*

النتيجة true لأن a* يمكن أن تمثل حرفي a.

معنى Dot

. يطابق حرفاً واحداً مهما كانت قيمته.

c.t

يمكن أن يطابق cat وcut وc9t.

معنى Star

* يعتمد على العنصر السابق.

a*

يمكن أن يطابق:

""
a
aa
aaa

لماذا Dynamic Programming؟

وجود * يعني أننا نملك عدة احتمالات: استخدام العنصر السابق صفر مرة أو مرة أو عدة مرات.

وهذه الفروع تؤدي إلى Subproblems متكررة، لذلك Dynamic Programming أو Memoization مناسبة جداً.

تعريف DP

dp[i][j]

يعني هل أول i أحرف من String تطابق أول j أحرف من Pattern بالكامل.

الحالة الأساسية:

dp[0][0] = true

ويمكن لـ Pattern مثل:

a*b*c*

أن يطابق String فارغاً لأن كل x* يمكن استخدامه صفر مرة.

الحرف العادي أو Dot

إذا كان الحرفان متساويين أو كان Pattern يحتوي .:

dp[i][j] = dp[i - 1][j - 1]

Star

يمكن أولاً تجاهل العنصر السابق مع *:

dp[i][j] = dp[i][j - 2]

وإذا كان العنصر السابق يطابق الحرف الحالي:

dp[i][j] = dp[i][j] || dp[i - 1][j]

لأن * يمكن أن يستهلك المزيد من الأحرف.

TypeScript

function isRegexMatch(s: string, p: string): boolean {
  const dp = Array.from(
    { length: s.length + 1 },
    () => new Array(p.length + 1).fill(false)
  );

  dp[0][0] = true;

  for (let j = 2; j <= p.length; j++) {
    if (p[j - 1] === '*') {
      dp[0][j] = dp[0][j - 2];
    }
  }

  for (let i = 1; i <= s.length; i++) {
    for (let j = 1; j <= p.length; j++) {
      if (
        p[j - 1] === '.' ||
        p[j - 1] === s[i - 1]
      ) {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (p[j - 1] === '*') {
        dp[i][j] = dp[i][j - 2];

        if (
          p[j - 2] === '.' ||
          p[j - 2] === s[i - 1]
        ) {
          dp[i][j] =
            dp[i][j] || dp[i - 1][j];
        }
      }
    }
  }

  return dp[s.length][p.length];
}

التعقيد

Time Complexity: O(n × m)
Space Complexity: O(n × m)

Regex مقابل Wildcard

في هذا النوع من Regex:

. → أي حرف واحد
* → تكرار العنصر السابق

أما Wildcard Matching فعادة يستخدم:

? → أي حرف واحد
* → أي سلسلة من الأحرف

لذلك معنى * مختلف تماماً.

أهمية .*

. يطابق أي حرف و* يسمح بتكراره، ولذلك:

.*

يمكن أن يطابق أي Sequence تقريباً.

Full Match

المطلوب هو مطابقة String بالكامل.

hello
ell

لا تعتبر Match في هذه المسألة رغم وجود ell داخل String.

الاستخدام العملي

Regex الحقيقي يستخدم في:

• Validation
• Search
• Log Filtering
• Data Processing
• Text Extraction

لكن في التطبيقات العملية نستخدم Regex Engine الجاهز للغة بدلاً من إعادة بناء هذه الخوارزمية.

سؤال مقابلات

المهم شرح حالتي *:

0 occurrence

و:

1 or more occurrences

إضافة إلى Initialization للـ Empty String.

الأخطاء الشائعة

• اعتبار * مستقلة عن الحرف السابق.
• اعتبارها صفر أو مرة واحدة فقط.
• نسيان Pattern الذي يمكنه مطابقة String فارغ.
• قبول Partial Match بدلاً من Full Match.

الخلاصة

Regular Expression Matching مثال ممتاز على تحويل Branching Logic إلى Dynamic Programming.

.  → any one character
x* → zero or more x

والحل القياسي يعمل في زمن O(n × m).