مسئله Regular Expression Matching یکی از مسائل معروف String Algorithms و Dynamic Programming است.

در نسخه کلاسیک این مسئله، یک String و یک Pattern داریم و Pattern می‌تواند شامل دو کاراکتر ویژه باشد:

.  → هر کاراکتر واحد
*  → صفر یا چند بار تکرار کاراکتر قبلی

برای مثال:

String:  aa
Pattern: a*

Pattern می‌گوید کاراکتر a می‌تواند صفر یا چند بار تکرار شود.

بنابراین:

aa matches a*

و پاسخ:

true

اما مسئله زمانی جالب می‌شود که چندین * و . در Pattern داشته باشیم.

این Regex با Regex واقعی چه تفاوتی دارد؟

Regex Engineهای واقعی بسیار پیچیده‌تر هستند و قابلیت‌هایی مانند این‌ها دارند:

+
?
[]
()
^
$
{n,m}
lookahead
lookbehind

اما در مسئله الگوریتمی کلاسیک معمولاً فقط این دو ویژگی داریم:

.
*

بنابراین هدف این مقاله ساخت یک Regex Engine کامل نیست؛ هدف درک منطق Pattern Matching با Dynamic Programming است.

معنی Dot چیست؟

کاراکتر:

با هر یک کاراکتر Match می‌شود.

مثلاً:

Pattern: c.t

با این رشته‌ها Match می‌شود:

cat
cut
cot
c9t

اما با:

ct

Match نمی‌شود، زیرا . دقیقاً یک کاراکتر را پوشش می‌دهد.

معنی Star چیست؟

کاراکتر:

به کاراکتر یا Pattern Element قبلی مربوط است و یعنی:

zero or more occurrences

مثلاً:

a*

می‌تواند با همه این‌ها Match شود:

""
a
aa
aaa
aaaa

چون تعداد a می‌تواند صفر، یک یا چند باشد.

چند مثال ساده

مثال اول

String:  aa
Pattern: a

Pattern فقط یک a دارد، پس:

false

مثال دوم

String:  aa
Pattern: a*

a* می‌تواند دو a را پوشش دهد:

true

مثال سوم

String:  ab
Pattern: .*

. با هر کاراکتر Match می‌شود و * اجازه تکرار می‌دهد.

پس:

.*

می‌تواند تقریباً هر Stringای را پوشش دهد.

نتیجه:

true

مثال چهارم

String:  aab
Pattern: c*a*b

c* می‌تواند صفر بار ظاهر شود.

a* می‌تواند دو a را بگیرد.

و b نیز با آخرین کاراکتر Match می‌شود.

پس:

true

چرا این مسئله سخت‌تر از Match ساده است؟

اگر Pattern فقط حروف معمولی و . داشت، کافی بود دو String را از چپ به راست مقایسه کنیم.

اما * باعث ایجاد چند تصمیم می‌شود.

مثلاً:

a*

ممکن است:

0 بار a
1 بار a
2 بار a
3 بار a
...

را پوشش دهد.

بنابراین باید تصمیم بگیریم هر * چند کاراکتر از String را Consume کند.

همین Branching باعث می‌شود Dynamic Programming راه‌حل مناسبی باشد.

تعریف حالت DP

فرض کنیم:

s = string
p = pattern

تعریف می‌کنیم:

dp[i][j]

یعنی:

آیا اولین i کاراکتر از s با اولین j کاراکتر از p Match می‌شود؟

پس:

dp[s.length][p.length]

پاسخ نهایی مسئله است.

Base Case اصلی

یک String خالی با Pattern خالی Match می‌شود:

dp[0][0] = true

اما String غیرخالی با Pattern خالی Match نمی‌شود:

dp[i][0] = false

برای:

dp[0][j]

ممکن است بعضی Patternها با String خالی Match شوند.

مثلاً:

a*b*c*

چون هر بخش x* می‌تواند صفر بار استفاده شود.

مقداردهی Pattern برای String خالی

اگر:

p[j - 1] === '*'

باشد، می‌توانیم Element قبلی و * را حذف کنیم:

dp[0][j] = dp[0][j - 2]

برای مثال:

Pattern: a*

می‌تواند String خالی را Match کند.

همچنین:

a*b*c*

نیز می‌تواند.

حالت اول: کاراکترهای معمولی یا Dot

اگر Pattern فعلی * نباشد، دو کاراکتر زمانی Compatible هستند که:

s[i - 1] === p[j - 1]

یا:

p[j - 1] === '.'

در این صورت:

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

یعنی اگر Prefixهای قبلی Match باشند، این دو کاراکتر نیز می‌توانند Match را ادامه دهند.

حالت دوم: Star

اگر:

p[j - 1] === '*'

باشد، دو حالت اصلی داریم.

حالت A: صفر بار استفاده از Element قبلی

مثلاً:

a*

را کاملاً Ignore کنیم.

در این صورت:

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

یعنی Element قبلی و * را حذف می‌کنیم.

حالت B: یک یا چند بار استفاده

اگر کاراکتر قبلی Pattern با String فعلی Match شود:

p[j - 2] === s[i - 1]

یا:

p[j - 2] === '.'

آنگاه * می‌تواند String فعلی را Consume کند.

پس:

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

توجه کنید j ثابت می‌ماند، چون همان * ممکن است دوباره کاراکتر بعدی را نیز پوشش دهد.

رابطه کامل DP

اگر Pattern فعلی * نباشد:

if chars match:
    dp[i][j] = dp[i - 1][j - 1]

اگر * باشد:

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

و اگر Element قبل از * با کاراکتر فعلی Match شود:

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

مثال مهم

فرض کنید:

s = "aab"
p = "c*a*b"

مرحله اول:

c*

می‌تواند صفر بار استفاده شود.

پس عملاً Pattern می‌شود:

a*b

سپس:

a*

دو a را Consume می‌کند.

در نهایت:

با b Match می‌شود.

نتیجه:

true

پیاده‌سازی TypeScript

function isRegexMatch(
  s: string,
  p: string
): boolean {
  const rows = s.length + 1;
  const cols = p.length + 1;

  const dp: boolean[][] = Array.from(
    { length: rows },
    () => new Array(cols).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++) {
      const patternChar = p[j - 1];
      const stringChar = s[i - 1];

      if (
        patternChar === '.' ||
        patternChar === stringChar
      ) {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (patternChar === '*') {
        dp[i][j] = dp[i][j - 2];

        const previousPatternChar = p[j - 2];

        if (
          previousPatternChar === '.' ||
          previousPatternChar === stringChar
        ) {
          dp[i][j] =
            dp[i][j] || dp[i - 1][j];
        }
      }
    }
  }

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

مثال:

console.log(isRegexMatch("aa", "a*"));
// true

console.log(isRegexMatch("ab", ".*"));
// true

console.log(isRegexMatch("aab", "c*a*b"));
// true

console.log(isRegexMatch("mississippi", "mis*is*p*."));
// false

جدول DP چه چیزی را نشان می‌دهد؟

برای هر Cell سؤال این است:

آیا prefix رشته تا اینجا
با prefix pattern تا اینجا
کاملاً match می‌شود؟

این نکته مهم است:

مسئله دنبال Partial Match نیست.

مثلاً اگر:

s = "hello"
p = "ell"

باشد، جواب این مسئله:

false

است، چون Pattern باید کل String را Match کند.

این با Search کردن Regex داخل String متفاوت است.

پیچیدگی زمانی

اگر طول String برابر n و Pattern برابر m باشد:

Time Complexity: O(n × m)

زیرا هر Cell جدول DP یک بار بررسی می‌شود.

فضای حافظه:

Space Complexity: O(n × m)

برای نسخه کامل Matrix.

آیا Space را می‌توان بهینه کرد؟

از نظر تئوری بله، زیرا بسیاری از Stateها فقط به Row فعلی و قبلی نیاز دارند.

اما به دلیل وابستگی‌های *، پیاده‌سازی بهینه‌شده کمی حساس‌تر است.

برای مصاحبه و خوانایی، Matrix کامل معمولاً انتخاب مناسبی است.

در صورت نیاز می‌توان Space را تقریباً به:

O(m)

کاهش داد.

روش Recursive

می‌توان مسئله را به صورت Recursive نیز تعریف کرد.

ابتدا بررسی می‌کنیم آیا اولین کاراکتر Match می‌شود:

firstMatch =
  s[0] === p[0]
  OR
  p[0] === '.'

اگر دومین کاراکتر Pattern * باشد، دو حالت داریم:

skip x*

یا:

consume one matching character

شبه‌منطق:

match(s, p):
    firstMatch = ...

    if p[1] == '*':
        return match(s, p[2:])
            OR
            (firstMatch AND match(s[1:], p))

    return firstMatch AND match(s[1:], p[1:])

این تعریف بسیار زیباست، اما بدون Memoization ممکن است بسیار کند شود.

چرا Recursion ساده کند می‌شود؟

Patternهایی مانند:

a*a*a*a*a*b

می‌توانند Branchهای زیادی ایجاد کنند.

هر * چند تصمیم ایجاد می‌کند و بسیاری از Subproblemها چند بار محاسبه می‌شوند.

در نتیجه نسخه Naive Recursive می‌تواند رفتار Exponential داشته باشد.

Memoization یا Dynamic Programming این محاسبات تکراری را حذف می‌کند.

Top-Down با Memoization

نمونه TypeScript:

function isRegexMatchMemo(
  s: string,
  p: string
): boolean {
  const memo = new Map<string, boolean>();

  function dfs(i: number, j: number): boolean {
    const key = `${i}:${j}`;

    if (memo.has(key)) {
      return memo.get(key)!;
    }

    if (j === p.length) {
      return i === s.length;
    }

    const firstMatch =
      i < s.length &&
      (p[j] === '.' || p[j] === s[i]);

    let result: boolean;

    if (
      j + 1 < p.length &&
      p[j + 1] === '*'
    ) {
      result =
        dfs(i, j + 2) ||
        (firstMatch && dfs(i + 1, j));
    } else {
      result =
        firstMatch && dfs(i + 1, j + 1);
    }

    memo.set(key, result);
    return result;
  }

  return dfs(0, 0);
}

این نسخه از نظر مفهومی برای بعضی افراد حتی ساده‌تر از Bottom-Up DP است.

معنی دو Branch در Star

این بخش مهم‌ترین قسمت الگوریتم است.

فرض کنید Pattern داریم:

a*

Branch اول:

dfs(i, j + 2)

یعنی:

a* را صفر بار استفاده کن.

Branch دوم:

firstMatch && dfs(i + 1, j)

یعنی:

یک a را Consume کن، ولی Pattern را روی a* نگه دار چون ممکن است دوباره استفاده شود.

همین دو تصمیم تمام رفتار * را مدل می‌کنند.

Regular Expression Matching در برابر Wildcard Matching

این دو مسئله گاهی اشتباه گرفته می‌شوند.

در Regex Matching کلاسیک:

. → any single character
* → repeat previous element

اما در Wildcard Matching معمولاً:

? → any single character
* → any sequence of characters

بنابراین معنای * کاملاً متفاوت است.

مثلاً در Regex:

a*

فقط تکرار a است.

اما در Wildcard:

می‌تواند هر Sequenceای را پوشش دهد.

چرا `.*` بسیار قدرتمند است؟

در Regex کلاسیک:

هر کاراکتر را Match می‌کند.

و:

اجازه تکرار می‌دهد.

پس:

.*

یعنی:

صفر یا چند عدد از هر کاراکتر.

به همین دلیل تقریباً هر Stringای را Match می‌کند.

Patternهای خالی‌شونده

بعضی Patternها می‌توانند String خالی را Match کنند:

a*

a*b*c*

.*

ولی:

a*b*c

نمی‌تواند String خالی را Match کند، چون c اجباری است.

این موضوع یکی از مهم‌ترین Edge Caseهای initialization جدول DP است.

کاربرد واقعی Regex Matching

در برنامه‌های واقعی معمولاً Regex Engine آماده زبان یا Runtime استفاده می‌شود.

مثلاً JavaScript:

const regex = /^a.*b$/;
regex.test("axxxb");

هدف این الگوریتم جایگزین کردن Regex Engine JavaScript نیست.

اما فهم آن برای Developer مهم است، زیرا نشان می‌دهد Pattern Matching چگونه می‌تواند به مسئله‌ای شامل State، Branching و Memoization تبدیل شود.

Validation

Regex در سیستم‌های واقعی برای Validation بسیار استفاده می‌شود.

مثلاً:

Email-like formats
Phone numbers
Usernames
IDs
URL patterns
Input rules

البته برای بسیاری از داده‌های استاندارد، Validation فقط با Regex کافی نیست و Business Rules نیز باید بررسی شوند.

Search و Filtering

Regex می‌تواند در ابزارهای Search، Log Viewer، Code Editor و Data Processing استفاده شود.

مثلاً:

ERROR.*timeout

می‌تواند برای پیدا کردن Logهایی با ساختاری مشابه استفاده شود.

اما الگوریتمی که در این مقاله ساختیم، فقط subset ساده‌ای از Regex را پشتیبانی می‌کند.

Security و Regex

Regexها در بعضی شرایط می‌توانند مسئله Performance ایجاد کنند.

برخی Regex Engineها ممکن است روی Patternهای خاص دچار Backtracking شدید شوند.

این موضوع با نام:

ReDoS
Regular Expression Denial of Service

شناخته می‌شود.

الگوریتم DP مورد بحث ما Backtracking Engine واقعی نیست، اما شناخت Complexity Regex در سیستم‌های Production مهم است.

کاربرد در Compiler و Parser Concepts

Regular Expressionها ارتباط نزدیکی با Finite Automata دارند.

Regexها را می‌توان به ساختارهایی مانند:

تبدیل کرد.

Regex Engineهای واقعی بسته به طراحی ممکن است از Automata، Backtracking VM یا ترکیبی از روش‌ها استفاده کنند.

بنابراین Regex Matching پلی میان String Algorithms، Formal Languages و Compiler Theory نیز محسوب می‌شود.

یک سؤال کلاسیک مصاحبه

صورت مسئله معمولاً چنین است:

یک String s و Pattern p داده شده است. Pattern فقط از حروف، . و * تشکیل شده. بررسی کنید آیا Pattern کل String را Match می‌کند یا خیر.

مثلاً:

s = "aab"
p = "c*a*b"

پاسخ:

true

یک پاسخ خوب باید توضیح دهد:

. یعنی چه.
* به Element قبلی وابسته است.
dp[i][j] چه معنایی دارد.
* دو حالت صفر بار و یک/چند بار دارد.
Patternهای x* چگونه String خالی را Match می‌کنند.
Complexity برابر O(n × m) است.

اشتباه رایج اول: تصور اینکه `*` مستقل است

در Regex کلاسیک:

به تنهایی معنایی ندارد.

این کاراکتر به Element قبلی وابسته است.

مثلاً:

a*

یعنی تکرار a.

.*

یعنی تکرار هر کاراکتر.

اشتباه رایج دوم: فقط یک بار استفاده از Star

* فقط صفر یا یک بار نیست.

بلکه:

0, 1, 2, 3, ...

بار می‌تواند Element قبلی را پوشش دهد.

به همین دلیل هنگام Consume کردن String، Pattern Pointer روی همان Star باقی می‌ماند.

اشتباه رایج سوم: نادیده گرفتن String خالی

مثلاً:

s = ""
p = "a*b*c*"

باید:

true

باشد.

اگر Initialization جدول DP به درستی انجام نشده باشد، این مورد اشتباه جواب داده می‌شود.

اشتباه رایج چهارم: Partial Match به جای Full Match

اگر:

s = "abcdef"
p = "bcd"

Pattern در String وجود دارد، اما کل String را پوشش نمی‌دهد.

در تعریف این مسئله پاسخ:

false

است.

Edge Caseها

s = ""
p = ""
→ true

s = ""
p = "a*"
→ true

s = "a"
p = "."
→ true

s = "abc"
p = ".*"
→ true

s = "abc"
p = "abcd*"
→ true

چرا مورد آخر true است؟ چون d* می‌تواند صفر بار استفاده شود و abc باقی می‌ماند.

Bottom-Up یا Top-Down؟

هر دو روش معتبرند.

Top-Down + Memoization

مزایا:

منطق * طبیعی‌تر دیده می‌شود.
کد نزدیک‌تر به تعریف Recursive مسئله است.

Bottom-Up DP

مزایا:

رفتار Complexity واضح است.
Call Stack ندارد.
جدول Stateها قابل مشاهده است.

در مصاحبه، هر دو انتخاب مناسب هستند اگر درست تحلیل شوند.

جمع‌بندی

Regular Expression Matching با . و * نمونه بسیار خوبی از مسئله‌ای است که از String Matching ساده به Dynamic Programming تبدیل می‌شود.

قواعد اصلی:

.  → هر یک کاراکتر
x* → صفر یا چند بار x

در DP تعریف می‌کنیم:

dp[i][j]

که مشخص می‌کند آیا Prefixهای String و Pattern تا آن نقطه Match می‌شوند.

برای * دو تصمیم اصلی داریم:

Use zero times
→ dp[i][j - 2]

یا:

Consume one matching character
→ dp[i - 1][j]

پیچیدگی نسخه DP:

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

مهم‌ترین چیزی که از این الگوریتم باید یاد گرفت فقط Regex نیست؛ بلکه نحوه تبدیل یک مسئله دارای Branching و Subproblemهای تکراری به Dynamic Programming است.

مسئله Regular Expression Matching یکی از مسائل معروف String Algorithms و Dynamic Programming است.

در نسخه کلاسیک این مسئله، یک String و یک Pattern داریم و Pattern می‌تواند شامل دو کاراکتر ویژه باشد:

.  → هر کاراکتر واحد
*  → صفر یا چند بار تکرار کاراکتر قبلی

برای مثال:

String:  aa
Pattern: a*

Pattern می‌گوید کاراکتر a می‌تواند صفر یا چند بار تکرار شود.

بنابراین:

aa matches a*

و پاسخ:

true

اما مسئله زمانی جالب می‌شود که چندین * و . در Pattern داشته باشیم.

این Regex با Regex واقعی چه تفاوتی دارد؟

Regex Engineهای واقعی بسیار پیچیده‌تر هستند و قابلیت‌هایی مانند این‌ها دارند:

+
?
[]
()
^
$
{n,m}
lookahead
lookbehind

اما در مسئله الگوریتمی کلاسیک معمولاً فقط این دو ویژگی داریم:

.
*

بنابراین هدف این مقاله ساخت یک Regex Engine کامل نیست؛ هدف درک منطق Pattern Matching با Dynamic Programming است.

معنی Dot چیست؟

کاراکتر:

با هر یک کاراکتر Match می‌شود.

مثلاً:

Pattern: c.t

با این رشته‌ها Match می‌شود:

cat
cut
cot
c9t

اما با:

ct

Match نمی‌شود، زیرا . دقیقاً یک کاراکتر را پوشش می‌دهد.

معنی Star چیست؟

کاراکتر:

به کاراکتر یا Pattern Element قبلی مربوط است و یعنی:

zero or more occurrences

مثلاً:

a*

می‌تواند با همه این‌ها Match شود:

""
a
aa
aaa
aaaa

چون تعداد a می‌تواند صفر، یک یا چند باشد.

چند مثال ساده

مثال اول

String:  aa
Pattern: a

Pattern فقط یک a دارد، پس:

false

مثال دوم

String:  aa
Pattern: a*

a* می‌تواند دو a را پوشش دهد:

true

مثال سوم

String:  ab
Pattern: .*

. با هر کاراکتر Match می‌شود و * اجازه تکرار می‌دهد.

پس:

.*

می‌تواند تقریباً هر Stringای را پوشش دهد.

نتیجه:

true

مثال چهارم

String:  aab
Pattern: c*a*b

c* می‌تواند صفر بار ظاهر شود.

a* می‌تواند دو a را بگیرد.

و b نیز با آخرین کاراکتر Match می‌شود.

پس:

true

چرا این مسئله سخت‌تر از Match ساده است؟

اگر Pattern فقط حروف معمولی و . داشت، کافی بود دو String را از چپ به راست مقایسه کنیم.

اما * باعث ایجاد چند تصمیم می‌شود.

مثلاً:

a*

ممکن است:

0 بار a
1 بار a
2 بار a
3 بار a
...

را پوشش دهد.

بنابراین باید تصمیم بگیریم هر * چند کاراکتر از String را Consume کند.

همین Branching باعث می‌شود Dynamic Programming راه‌حل مناسبی باشد.

تعریف حالت DP

فرض کنیم:

s = string
p = pattern

تعریف می‌کنیم:

dp[i][j]

یعنی:

آیا اولین i کاراکتر از s با اولین j کاراکتر از p Match می‌شود؟

پس:

dp[s.length][p.length]

پاسخ نهایی مسئله است.

Base Case اصلی

یک String خالی با Pattern خالی Match می‌شود:

dp[0][0] = true

اما String غیرخالی با Pattern خالی Match نمی‌شود:

dp[i][0] = false

برای:

dp[0][j]

ممکن است بعضی Patternها با String خالی Match شوند.

مثلاً:

a*b*c*

چون هر بخش x* می‌تواند صفر بار استفاده شود.

مقداردهی Pattern برای String خالی

اگر:

p[j - 1] === '*'

باشد، می‌توانیم Element قبلی و * را حذف کنیم:

dp[0][j] = dp[0][j - 2]

برای مثال:

Pattern: a*

می‌تواند String خالی را Match کند.

همچنین:

a*b*c*

نیز می‌تواند.

حالت اول: کاراکترهای معمولی یا Dot

اگر Pattern فعلی * نباشد، دو کاراکتر زمانی Compatible هستند که:

s[i - 1] === p[j - 1]

یا:

p[j - 1] === '.'

در این صورت:

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

یعنی اگر Prefixهای قبلی Match باشند، این دو کاراکتر نیز می‌توانند Match را ادامه دهند.

حالت دوم: Star

اگر:

p[j - 1] === '*'

باشد، دو حالت اصلی داریم.

حالت A: صفر بار استفاده از Element قبلی

مثلاً:

a*

را کاملاً Ignore کنیم.

در این صورت:

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

یعنی Element قبلی و * را حذف می‌کنیم.

حالت B: یک یا چند بار استفاده

اگر کاراکتر قبلی Pattern با String فعلی Match شود:

p[j - 2] === s[i - 1]

یا:

p[j - 2] === '.'

آنگاه * می‌تواند String فعلی را Consume کند.

پس:

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

توجه کنید j ثابت می‌ماند، چون همان * ممکن است دوباره کاراکتر بعدی را نیز پوشش دهد.

رابطه کامل DP

اگر Pattern فعلی * نباشد:

if chars match:
    dp[i][j] = dp[i - 1][j - 1]

اگر * باشد:

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

و اگر Element قبل از * با کاراکتر فعلی Match شود:

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

مثال مهم

فرض کنید:

s = "aab"
p = "c*a*b"

مرحله اول:

c*

می‌تواند صفر بار استفاده شود.

پس عملاً Pattern می‌شود:

a*b

سپس:

a*

دو a را Consume می‌کند.

در نهایت:

با b Match می‌شود.

نتیجه:

true

پیاده‌سازی TypeScript

function isRegexMatch(
  s: string,
  p: string
): boolean {
  const rows = s.length + 1;
  const cols = p.length + 1;

  const dp: boolean[][] = Array.from(
    { length: rows },
    () => new Array(cols).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++) {
      const patternChar = p[j - 1];
      const stringChar = s[i - 1];

      if (
        patternChar === '.' ||
        patternChar === stringChar
      ) {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (patternChar === '*') {
        dp[i][j] = dp[i][j - 2];

        const previousPatternChar = p[j - 2];

        if (
          previousPatternChar === '.' ||
          previousPatternChar === stringChar
        ) {
          dp[i][j] =
            dp[i][j] || dp[i - 1][j];
        }
      }
    }
  }

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

مثال:

console.log(isRegexMatch("aa", "a*"));
// true

console.log(isRegexMatch("ab", ".*"));
// true

console.log(isRegexMatch("aab", "c*a*b"));
// true

console.log(isRegexMatch("mississippi", "mis*is*p*."));
// false

جدول DP چه چیزی را نشان می‌دهد؟

برای هر Cell سؤال این است:

آیا prefix رشته تا اینجا
با prefix pattern تا اینجا
کاملاً match می‌شود؟

این نکته مهم است:

مسئله دنبال Partial Match نیست.

مثلاً اگر:

s = "hello"
p = "ell"

باشد، جواب این مسئله:

false

است، چون Pattern باید کل String را Match کند.

این با Search کردن Regex داخل String متفاوت است.

پیچیدگی زمانی

اگر طول String برابر n و Pattern برابر m باشد:

Time Complexity: O(n × m)

زیرا هر Cell جدول DP یک بار بررسی می‌شود.

فضای حافظه:

Space Complexity: O(n × m)

برای نسخه کامل Matrix.

آیا Space را می‌توان بهینه کرد؟

از نظر تئوری بله، زیرا بسیاری از Stateها فقط به Row فعلی و قبلی نیاز دارند.

اما به دلیل وابستگی‌های *، پیاده‌سازی بهینه‌شده کمی حساس‌تر است.

برای مصاحبه و خوانایی، Matrix کامل معمولاً انتخاب مناسبی است.

در صورت نیاز می‌توان Space را تقریباً به:

O(m)

کاهش داد.

روش Recursive

می‌توان مسئله را به صورت Recursive نیز تعریف کرد.

ابتدا بررسی می‌کنیم آیا اولین کاراکتر Match می‌شود:

firstMatch =
  s[0] === p[0]
  OR
  p[0] === '.'

اگر دومین کاراکتر Pattern * باشد، دو حالت داریم:

skip x*

یا:

consume one matching character

شبه‌منطق:

match(s, p):
    firstMatch = ...

    if p[1] == '*':
        return match(s, p[2:])
            OR
            (firstMatch AND match(s[1:], p))

    return firstMatch AND match(s[1:], p[1:])

این تعریف بسیار زیباست، اما بدون Memoization ممکن است بسیار کند شود.

چرا Recursion ساده کند می‌شود؟

Patternهایی مانند:

a*a*a*a*a*b

می‌توانند Branchهای زیادی ایجاد کنند.

هر * چند تصمیم ایجاد می‌کند و بسیاری از Subproblemها چند بار محاسبه می‌شوند.

در نتیجه نسخه Naive Recursive می‌تواند رفتار Exponential داشته باشد.

Memoization یا Dynamic Programming این محاسبات تکراری را حذف می‌کند.

Top-Down با Memoization

نمونه TypeScript:

function isRegexMatchMemo(
  s: string,
  p: string
): boolean {
  const memo = new Map<string, boolean>();

  function dfs(i: number, j: number): boolean {
    const key = `${i}:${j}`;

    if (memo.has(key)) {
      return memo.get(key)!;
    }

    if (j === p.length) {
      return i === s.length;
    }

    const firstMatch =
      i < s.length &&
      (p[j] === '.' || p[j] === s[i]);

    let result: boolean;

    if (
      j + 1 < p.length &&
      p[j + 1] === '*'
    ) {
      result =
        dfs(i, j + 2) ||
        (firstMatch && dfs(i + 1, j));
    } else {
      result =
        firstMatch && dfs(i + 1, j + 1);
    }

    memo.set(key, result);
    return result;
  }

  return dfs(0, 0);
}

این نسخه از نظر مفهومی برای بعضی افراد حتی ساده‌تر از Bottom-Up DP است.

معنی دو Branch در Star

این بخش مهم‌ترین قسمت الگوریتم است.

فرض کنید Pattern داریم:

a*

Branch اول:

dfs(i, j + 2)

یعنی:

a* را صفر بار استفاده کن.

Branch دوم:

firstMatch && dfs(i + 1, j)

یعنی:

یک a را Consume کن، ولی Pattern را روی a* نگه دار چون ممکن است دوباره استفاده شود.

همین دو تصمیم تمام رفتار * را مدل می‌کنند.

Regular Expression Matching در برابر Wildcard Matching

این دو مسئله گاهی اشتباه گرفته می‌شوند.

در Regex Matching کلاسیک:

. → any single character
* → repeat previous element

اما در Wildcard Matching معمولاً:

? → any single character
* → any sequence of characters

بنابراین معنای * کاملاً متفاوت است.

مثلاً در Regex:

a*

فقط تکرار a است.

اما در Wildcard:

می‌تواند هر Sequenceای را پوشش دهد.

چرا `.*` بسیار قدرتمند است؟

در Regex کلاسیک:

هر کاراکتر را Match می‌کند.

و:

اجازه تکرار می‌دهد.

پس:

.*

یعنی:

صفر یا چند عدد از هر کاراکتر.

به همین دلیل تقریباً هر Stringای را Match می‌کند.

Patternهای خالی‌شونده

بعضی Patternها می‌توانند String خالی را Match کنند:

a*

a*b*c*

.*

ولی:

a*b*c

نمی‌تواند String خالی را Match کند، چون c اجباری است.

این موضوع یکی از مهم‌ترین Edge Caseهای initialization جدول DP است.

کاربرد واقعی Regex Matching

در برنامه‌های واقعی معمولاً Regex Engine آماده زبان یا Runtime استفاده می‌شود.

مثلاً JavaScript:

const regex = /^a.*b$/;
regex.test("axxxb");

هدف این الگوریتم جایگزین کردن Regex Engine JavaScript نیست.

Validation

Regex در سیستم‌های واقعی برای Validation بسیار استفاده می‌شود.

مثلاً:

Email-like formats
Phone numbers
Usernames
IDs
URL patterns
Input rules

البته برای بسیاری از داده‌های استاندارد، Validation فقط با Regex کافی نیست و Business Rules نیز باید بررسی شوند.

Search و Filtering

Regex می‌تواند در ابزارهای Search، Log Viewer، Code Editor و Data Processing استفاده شود.

مثلاً:

ERROR.*timeout

می‌تواند برای پیدا کردن Logهایی با ساختاری مشابه استفاده شود.

اما الگوریتمی که در این مقاله ساختیم، فقط subset ساده‌ای از Regex را پشتیبانی می‌کند.

Security و Regex

Regexها در بعضی شرایط می‌توانند مسئله Performance ایجاد کنند.

برخی Regex Engineها ممکن است روی Patternهای خاص دچار Backtracking شدید شوند.

این موضوع با نام:

ReDoS
Regular Expression Denial of Service

شناخته می‌شود.

الگوریتم DP مورد بحث ما Backtracking Engine واقعی نیست، اما شناخت Complexity Regex در سیستم‌های Production مهم است.

کاربرد در Compiler و Parser Concepts

Regular Expressionها ارتباط نزدیکی با Finite Automata دارند.

Regexها را می‌توان به ساختارهایی مانند:

تبدیل کرد.

Regex Engineهای واقعی بسته به طراحی ممکن است از Automata، Backtracking VM یا ترکیبی از روش‌ها استفاده کنند.

بنابراین Regex Matching پلی میان String Algorithms، Formal Languages و Compiler Theory نیز محسوب می‌شود.

یک سؤال کلاسیک مصاحبه

صورت مسئله معمولاً چنین است:

یک String s و Pattern p داده شده است. Pattern فقط از حروف، . و * تشکیل شده. بررسی کنید آیا Pattern کل String را Match می‌کند یا خیر.

مثلاً:

s = "aab"
p = "c*a*b"

پاسخ:

true

یک پاسخ خوب باید توضیح دهد:

. یعنی چه.
* به Element قبلی وابسته است.
dp[i][j] چه معنایی دارد.
* دو حالت صفر بار و یک/چند بار دارد.
Patternهای x* چگونه String خالی را Match می‌کنند.
Complexity برابر O(n × m) است.

اشتباه رایج اول: تصور اینکه `*` مستقل است

در Regex کلاسیک:

به تنهایی معنایی ندارد.

این کاراکتر به Element قبلی وابسته است.

مثلاً:

a*

یعنی تکرار a.

.*

یعنی تکرار هر کاراکتر.

اشتباه رایج دوم: فقط یک بار استفاده از Star

* فقط صفر یا یک بار نیست.

بلکه:

0, 1, 2, 3, ...

بار می‌تواند Element قبلی را پوشش دهد.

به همین دلیل هنگام Consume کردن String، Pattern Pointer روی همان Star باقی می‌ماند.

اشتباه رایج سوم: نادیده گرفتن String خالی

مثلاً:

s = ""
p = "a*b*c*"

باید:

true

باشد.

اگر Initialization جدول DP به درستی انجام نشده باشد، این مورد اشتباه جواب داده می‌شود.

اشتباه رایج چهارم: Partial Match به جای Full Match

اگر:

s = "abcdef"
p = "bcd"

Pattern در String وجود دارد، اما کل String را پوشش نمی‌دهد.

در تعریف این مسئله پاسخ:

false

است.

Edge Caseها

s = ""
p = ""
→ true

s = ""
p = "a*"
→ true

s = "a"
p = "."
→ true

s = "abc"
p = ".*"
→ true

s = "abc"
p = "abcd*"
→ true

چرا مورد آخر true است؟ چون d* می‌تواند صفر بار استفاده شود و abc باقی می‌ماند.

Bottom-Up یا Top-Down؟

هر دو روش معتبرند.

Top-Down + Memoization

مزایا:

منطق * طبیعی‌تر دیده می‌شود.
کد نزدیک‌تر به تعریف Recursive مسئله است.

Bottom-Up DP

مزایا:

رفتار Complexity واضح است.
Call Stack ندارد.
جدول Stateها قابل مشاهده است.

در مصاحبه، هر دو انتخاب مناسب هستند اگر درست تحلیل شوند.

جمع‌بندی

Regular Expression Matching با . و * نمونه بسیار خوبی از مسئله‌ای است که از String Matching ساده به Dynamic Programming تبدیل می‌شود.

قواعد اصلی:

.  → هر یک کاراکتر
x* → صفر یا چند بار x

در DP تعریف می‌کنیم:

dp[i][j]

که مشخص می‌کند آیا Prefixهای String و Pattern تا آن نقطه Match می‌شوند.

برای * دو تصمیم اصلی داریم:

Use zero times
→ dp[i][j - 2]

یا:

Consume one matching character
→ dp[i - 1][j]

پیچیدگی نسخه DP:

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

Regular Expression Matching چیست؟ آموزش Regex Matching با Dynamic Programming و TypeScript

این Regex با Regex واقعی چه تفاوتی دارد؟

معنی Dot چیست؟

معنی Star چیست؟

چند مثال ساده

مثال اول

مثال دوم

مثال سوم

مثال چهارم

چرا این مسئله سخت‌تر از Match ساده است؟

تعریف حالت DP

Base Case اصلی

مقداردهی Pattern برای String خالی

حالت اول: کاراکترهای معمولی یا Dot

حالت دوم: Star

حالت A: صفر بار استفاده از Element قبلی

حالت B: یک یا چند بار استفاده

رابطه کامل DP

مثال مهم

پیاده‌سازی TypeScript

جدول DP چه چیزی را نشان می‌دهد؟

پیچیدگی زمانی

آیا Space را می‌توان بهینه کرد؟

روش Recursive

چرا Recursion ساده کند می‌شود؟

Top-Down با Memoization

معنی دو Branch در Star

Regular Expression Matching در برابر Wildcard Matching

چرا .* بسیار قدرتمند است؟

Patternهای خالی‌شونده

کاربرد واقعی Regex Matching

Validation

Search و Filtering

Security و Regex

کاربرد در Compiler و Parser Concepts

یک سؤال کلاسیک مصاحبه

اشتباه رایج اول: تصور اینکه * مستقل است

اشتباه رایج دوم: فقط یک بار استفاده از Star

اشتباه رایج سوم: نادیده گرفتن String خالی

اشتباه رایج چهارم: Partial Match به جای Full Match

Edge Caseها

Bottom-Up یا Top-Down؟

Top-Down + Memoization

Bottom-Up DP

جمع‌بندی

الگوریتم Rabin–Karp چیست؟ جستجوی سریع رشته با Rolling Hash

B2B CRM و B2C CRM چه تفاوتی دارند؟ از فرآیند فروش تا معماری نرم‌افزار

Regular Expression Matching چیست؟ آموزش Regex Matching با Dynamic Programming و TypeScript

این Regex با Regex واقعی چه تفاوتی دارد؟

معنی Dot چیست؟

معنی Star چیست؟

چند مثال ساده

مثال اول

مثال دوم

مثال سوم

مثال چهارم

چرا این مسئله سخت‌تر از Match ساده است؟

تعریف حالت DP

Base Case اصلی

مقداردهی Pattern برای String خالی

حالت اول: کاراکترهای معمولی یا Dot

حالت دوم: Star

حالت A: صفر بار استفاده از Element قبلی

حالت B: یک یا چند بار استفاده

رابطه کامل DP

مثال مهم

پیاده‌سازی TypeScript

جدول DP چه چیزی را نشان می‌دهد؟

پیچیدگی زمانی

آیا Space را می‌توان بهینه کرد؟

روش Recursive

چرا Recursion ساده کند می‌شود؟

Top-Down با Memoization

معنی دو Branch در Star

Regular Expression Matching در برابر Wildcard Matching

چرا .* بسیار قدرتمند است؟

Patternهای خالی‌شونده

کاربرد واقعی Regex Matching

Validation

Search و Filtering

چرا `.*` بسیار قدرتمند است؟

اشتباه رایج اول: تصور اینکه `*` مستقل است

چرا `.*` بسیار قدرتمند است؟

اشتباه رایج اول: تصور اینکه `*` مستقل است