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

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

Code

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

برای مثال:

Code

String:  aa
Pattern: a*

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

بنابراین:

Code

aa matches a*

و پاسخ:

Code

true

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

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

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

Code

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

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

Code

.
*

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

معنی Dot چیست؟

کاراکتر:

Code

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

مثلاً:

Code

Pattern: c.t

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

Code

cat
cut
cot
c9t

اما با:

Code

ct

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

معنی Star چیست؟

کاراکتر:

Code

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

Code

zero or more occurrences

مثلاً:

Code

a*

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

Code

""
a
aa
aaa
aaaa

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

چند مثال ساده

مثال اول

Code

String:  aa
Pattern: a

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

Code

false

مثال دوم

Code

String:  aa
Pattern: a*

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

Code

true

مثال سوم

Code

String:  ab
Pattern: .*

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

پس:

Code

.*

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

نتیجه:

Code

true

مثال چهارم

Code

String:  aab
Pattern: c*a*b

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

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

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

پس:

Code

true

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

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

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

مثلاً:

Code

a*

ممکن است:

Code

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

را پوشش دهد.

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

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

تعریف حالت DP

فرض کنیم:

Code

s = string
p = pattern

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

Code

dp[i][j]

یعنی:

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

پس:

Code

dp[s.length][p.length]

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

Base Case اصلی

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

Code

dp[0][0] = true

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

Code

dp[i][0] = false

برای:

Code

dp[0][j]

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

مثلاً:

Code

a*b*c*

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

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

اگر:

Code

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

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

Code

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

برای مثال:

Code

Pattern: a*

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

همچنین:

Code

a*b*c*

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

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

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

Code

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

یا:

Code

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

در این صورت:

Code

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

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

حالت دوم: Star

اگر:

Code

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

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

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

مثلاً:

Code

a*

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

در این صورت:

Code

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

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

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

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

Code

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

یا:

Code

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

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

پس:

Code

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

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

رابطه کامل DP

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

Code

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

اگر * باشد:

Code

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

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

Code

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

مثال مهم

فرض کنید:

Code

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

مرحله اول:

Code

c*

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

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

Code

a*b

سپس:

Code

a*

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

در نهایت:

Code

با b Match می‌شود.

نتیجه:

Code

true

پیاده‌سازی TypeScript

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];
}

مثال:

TypeScript

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 سؤال این است:

Code

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

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

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

مثلاً اگر:

Code

s = "hello"
p = "ell"

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

Code

false

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

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

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

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

Code

Time Complexity: O(n × m)

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

فضای حافظه:

Code

Space Complexity: O(n × m)

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

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

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

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

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

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

Code

O(m)

کاهش داد.

روش Recursive

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

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

Code

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

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

Code

skip x*

یا:

Code

consume one matching character

شبه‌منطق:

Code

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هایی مانند:

Code

a*a*a*a*a*b

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

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

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

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

Top-Down با Memoization

نمونه TypeScript:

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 داریم:

Code

a*

Branch اول:

Code

dfs(i, j + 2)

یعنی:

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

Branch دوم:

Code

firstMatch && dfs(i + 1, j)

یعنی:

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

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

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

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

در Regex Matching کلاسیک:

Code

. → any single character
* → repeat previous element

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

Code

? → any single character
* → any sequence of characters

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

مثلاً در Regex:

Code

a*

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

اما در Wildcard:

Code

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

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

در Regex کلاسیک:

Code

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

و:

Code

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

پس:

Code

.*

یعنی:

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

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

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

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

Code

a*

Code

a*b*c*

Code

.*

ولی:

Code

a*b*c

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

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

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

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

مثلاً JavaScript:

TypeScript

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 استفاده شود.

مثلاً:

Code

ERROR.*timeout

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

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

Security و Regex

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

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

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

Code

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 می‌کند یا خیر.

مثلاً:

Code

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

پاسخ:

Code

true

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

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

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

در Regex کلاسیک:

Code

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

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

مثلاً:

Code

a*

یعنی تکرار a.

Code

.*

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

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

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

بلکه:

Code

0, 1, 2, 3, ...

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

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

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

مثلاً:

Code

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

باید:

Code

true

باشد.

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

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

اگر:

Code

s = "abcdef"
p = "bcd"

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

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

Code

false

است.

Edge Caseها

Code

s = ""
p = ""
→ true

Code

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

Code

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

Code

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

Code

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 تبدیل می‌شود.

قواعد اصلی:

Code

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

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

Code

dp[i][j]

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

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

Code

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

یا:

Code

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

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

Code

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 می‌تواند شامل دو کاراکتر ویژه باشد:

Code

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

برای مثال:

Code

String:  aa
Pattern: a*

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

بنابراین:

Code

aa matches a*

و پاسخ:

Code

true

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

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

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

Code

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

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

Code

.
*

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

معنی Dot چیست؟

کاراکتر:

Code

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

مثلاً:

Code

Pattern: c.t

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

Code

cat
cut
cot
c9t

اما با:

Code

ct

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

معنی Star چیست؟

کاراکتر:

Code

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

Code

zero or more occurrences

مثلاً:

Code

a*

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

Code

""
a
aa
aaa
aaaa

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

چند مثال ساده

مثال اول

Code

String:  aa
Pattern: a

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

Code

false

مثال دوم

Code

String:  aa
Pattern: a*

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

Code

true

مثال سوم

Code

String:  ab
Pattern: .*

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

پس:

Code

.*

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

نتیجه:

Code

true

مثال چهارم

Code

String:  aab
Pattern: c*a*b

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

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

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

پس:

Code

true

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

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

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

مثلاً:

Code

a*

ممکن است:

Code

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

را پوشش دهد.

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

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

تعریف حالت DP

فرض کنیم:

Code

s = string
p = pattern

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

Code

dp[i][j]

یعنی:

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

پس:

Code

dp[s.length][p.length]

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

Base Case اصلی

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

Code

dp[0][0] = true

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

Code

dp[i][0] = false

برای:

Code

dp[0][j]

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

مثلاً:

Code

a*b*c*

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

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

اگر:

Code

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

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

Code

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

برای مثال:

Code

Pattern: a*

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

همچنین:

Code

a*b*c*

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

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

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

Code

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

یا:

Code

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

در این صورت:

Code

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

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

حالت دوم: Star

اگر:

Code

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

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

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

مثلاً:

Code

a*

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

در این صورت:

Code

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

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

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

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

Code

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

یا:

Code

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

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

پس:

Code

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

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

رابطه کامل DP

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

Code

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

اگر * باشد:

Code

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

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

Code

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

مثال مهم

فرض کنید:

Code

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

مرحله اول:

Code

c*

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

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

Code

a*b

سپس:

Code

a*

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

در نهایت:

Code

با b Match می‌شود.

نتیجه:

Code

true

پیاده‌سازی TypeScript

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];
}

مثال:

TypeScript

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 سؤال این است:

Code

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

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

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

مثلاً اگر:

Code

s = "hello"
p = "ell"

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

Code

false

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

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

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

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

Code

Time Complexity: O(n × m)

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

فضای حافظه:

Code

Space Complexity: O(n × m)

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

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

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

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

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

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

Code

O(m)

کاهش داد.

روش Recursive

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

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

Code

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

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

Code

skip x*

یا:

Code

consume one matching character

شبه‌منطق:

Code

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هایی مانند:

Code

a*a*a*a*a*b

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

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

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

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

Top-Down با Memoization

نمونه TypeScript:

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 داریم:

Code

a*

Branch اول:

Code

dfs(i, j + 2)

یعنی:

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

Branch دوم:

Code

firstMatch && dfs(i + 1, j)

یعنی:

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

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

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

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

در Regex Matching کلاسیک:

Code

. → any single character
* → repeat previous element

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

Code

? → any single character
* → any sequence of characters

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

مثلاً در Regex:

Code

a*

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

اما در Wildcard:

Code

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

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

در Regex کلاسیک:

Code

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

و:

Code

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

پس:

Code

.*

یعنی:

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

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

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

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

Code

a*

Code

a*b*c*

Code

.*

ولی:

Code

a*b*c

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

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

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

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

مثلاً JavaScript:

TypeScript

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 استفاده شود.

مثلاً:

Code

ERROR.*timeout

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

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

Security و Regex

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

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

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

Code

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 می‌کند یا خیر.

مثلاً:

Code

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

پاسخ:

Code

true

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

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

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

در Regex کلاسیک:

Code

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

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

مثلاً:

Code

a*

یعنی تکرار a.

Code

.*

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

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

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

بلکه:

Code

0, 1, 2, 3, ...

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

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

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

مثلاً:

Code

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

باید:

Code

true

باشد.

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

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

اگر:

Code

s = "abcdef"
p = "bcd"

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

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

Code

false

است.

Edge Caseها

Code

s = ""
p = ""
→ true

Code

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

Code

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

Code

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

Code

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 تبدیل می‌شود.

قواعد اصلی:

Code

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

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

Code

dp[i][j]

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

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

Code

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

یا:

Code

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

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

Code

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

جمع‌بندی

Palindrome چیست؟ آموزش تشخیص رشته‌های قرینه با Two Pointers و TypeScript

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

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

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

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

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

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