কনটেন্টে যান

022 — Regular Expression Matching

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • Original source: Classic regex (. and *) matching DP exercise
  • Platform: LeetCode — https://leetcode.com/problems/regular-expression-matching/
  • Topic: dynamic programming (string DP, hard transitions)
  • Difficulty: Hard
  • Pattern: String DP, hard transitions
  • Basic idea inherited from: #17 LCS ও #18 Edit Distance — একই two-prefix dp[i][j] grid, কিন্তু এখন pattern-এর * একটা চতুর "শূন্য বা একাধিক" শাখা যোগ করে

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা text s আর একটা pattern p দেওয়া। p-তে দুটো special character থাকতে পারে: . যেকোনো একটা character-এর সাথে মেলে, আর * মানে "ঠিক আগের character-টা শূন্য বা যত খুশি বার"। তোমাকে বলতে হবে p পুরো s-এর সাথে মেলে কি না (পুরো string, কোনো অংশমাত্র নয়)।

উদাহরণ
s = "aab", p = "c*a*b"
c* -> শূন্যটা c, a* -> দুটো a, b -> b  => পুরো match  -> True

Input ও output

উদাহরণ
Input : s = "aa",  p = "a"     -> Output: False  (একটাই a মেলে, দুটো নয়)
Input : s = "aa",  p = "a*"    -> Output: True
Input : s = "ab",  p = ".*"    -> Output: True   (.* = যেকোনো কিছু)
Input : s = "aab", p = "c*a*b" -> Output: True
Input : s = "mississippi", p = "mis*is*p*." -> Output: False

Edge case 1: s = "", p = ""     -> Output: True
Edge case 2: s = "", p = "a*"   -> Output: True
Edge case 3: s = "a", p = ""    -> Output: False

চেনা উদাহরণে বোঝা

ভাবো তুমি একটা checklist (pattern) ধরে একটা লাইন (text) মেলাচ্ছ। বেশির ভাগ checklist-আইটেম একটা করে অক্ষর দাবি করে। কিন্তু *-ওয়ালা আইটেম একটা "যত খুশি" stamp — তুমি সিদ্ধান্ত নাও এটাকে একদমই না খাটানো (পরের আইটেমে চলে যাও) নাকি লাইনের আরেকটা অক্ষর খেয়ে একই stamp-এ থেকে যাওয়া। প্রতিটা মোড়ে এই দুই পথ চেষ্টা করো; কোনো পথে শেষ পর্যন্ত পুরোটা মিললেই হলো।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত্তি #17 LCS আর #18 Edit Distance-এর two-prefix dp[i][j] grid — s-এর প্রথম i character আর p-এর প্রথম j character match হয় কি না। নতুন কঠিন অংশ শুধু *: যখন p[j-1] একটা *, তখন সেটা আগের character-কে শূন্য বার (*-জোড়াটা বাদ) বা এক-বা-বেশি বার (একটা s-character খরচ করে একই *-এ থেকে যাওয়া) ব্যবহার করে। এই দুই-শাখার transition-ই এটাকে "hard" বানায়।

ভেতরের যুক্তি

লুকানো logic দুই ক্ষেত্রে ভাগ। (1) p[j-1] যদি * না হয়: তখন শেষ character-দুটো মিলতে হবে (p[j-1] == s[i-1] বা p[j-1] == '.'), আর তা মিললে প্রশ্ন diagonal-এ ছোট হয় (dp[i-1][j-1])। (2) p[j-1] যদি * হয়: দুই উপায় — zero বার, মানে * আর তার আগের character জোড়াটা বাদ (dp[i][j-2]); বা one+ বার, মানে আগের pattern-character s[i-1]-এর সাথে মেলে (p[j-2] == s[i-1] বা '.') এবং তখন একটা s-character খরচ করে একই * ধরে রাখা (dp[i-1][j])। এ দুটোর OR।

কী দিয়ে তথ্য রাখব

একটা 2D boolean array dp, size (m+1) x (n+1) যেখানে m = len(s), n = len(p)। dp[i][j] = s-এর প্রথম i character p-এর প্রথম j character-এর সাথে মেলে কি না। padding row/column খালি prefix বোঝায়; বিশেষ করে dp[0][j] সামলায় "p যদি a বা xy*... দিয়ে খালি string-এ মেলে"।

এটি কেন উপযুক্ত

State-এ দুটো progress লাগে — text-এ কতদূর, pattern-এ কতদূর — কারণ একটা * text-এর শূন্য বা একাধিক character গিলতে পারে, তাই দুই index আলাদা গতিতে এগোয়। boolean যথেষ্ট, কারণ আমরা শুধু "মেলে কি মেলে না" চাই, কোনো count বা cost নয়। padding cell base case-গুলো (বিশেষত dp[0][*]) পরিষ্কার রাখে।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: index দুটো নিয়ে recurse করো, * দেখলে দুই শাখা।

উদাহরণ
match(i, j):                     # s[i:] কি p[j:]-এর সাথে মেলে?
    if j == len(p): return i == len(s)
    first = i < len(s) and (p[j] == s[i] or p[j] == '.')
    if j+1 < len(p) and p[j+1] == '*':
        return match(i, j+2)                  # zero বার
            or (first and match(i+1, j))      # one+ বার
    return first and match(i+1, j+1)          # সাধারণ এক-character
answer = match(0, 0)

কোথায় বেশি কাজ হচ্ছে

প্রতিটা * দুটো শাখা খোলে, আর .*-জাতীয় pattern-এ একই (i, j) অসংখ্য পথে পৌঁছায় — তাই naive recursion exponential হয়ে যেতে পারে (overlapping subproblems)। অথচ আলাদা (i, j) জোড়ার সংখ্যা মাত্র (m+1) x (n+1), তাই memoize করলেই polynomial।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: ফলাফল শুধু দুই suffix-শুরু (i, j) (বা সমতুল্যভাবে দুই prefix-length)-এর উপর নির্ভর করে — সেখানে পৌঁছাতে *-গুলো কীভাবে expand করেছিল তাতে কিছু আসে যায় না। তাই প্রতিটা (i, j) একবার গুনে রাখাই যথেষ্ট।

আরও কম কাজে সমাধান

State (শব্দে): dp[i][j] = s-এর প্রথম i-টা character p-এর প্রথম j-টা character-এর সাথে পুরোপুরি মেলে কি না (boolean)।

Transition:

উদাহরণ
if p[j-1] != '*':
    dp[i][j] = dp[i-1][j-1] and (p[j-1] == s[i-1] or p[j-1] == '.')
else:  # p[j-1] == '*', জোড়া হলো p[j-2] p[j-1]
    dp[i][j] = dp[i][j-2]                                  # p[j-2] শূন্য বার
    if p[j-2] == s[i-1] or p[j-2] == '.':
        dp[i][j] = dp[i][j] or dp[i-1][j]                 # p[j-2] এক-বা-বেশি বার

Base case: dp[0][0] = True; dp[0][j] = pattern যদি x* জোড়া দিয়ে খালি string-এ মেলে (p[j-1]=='*' হলে dp[0][j] = dp[0][j-2])। dp[i][0] = False for i > 0।

Answer location: dp[m][n]।

Fill order: row by row (i = 0..m), প্রতিটা row-তে বাঁ থেকে ডানে (j); i=0 row আলাদা ভরো base হিসেবে। সব dependency (diagonal, উপর, j-2 বাঁ) আগেই filled।

ভাবনার পরিবর্তন

মোচড়: *-কে একটা single character ভেবো না — ভাবো এটা ঠিক আগের character-এর সাথে জোড়া বেঁধে একটা "শূন্য-বা-বেশি" block বানায়। প্রতিটা এমন block-এ মাত্র দুটো প্রশ্ন: "block-টা একদম বাদ দিই (j-2-এ লাফ)?" নাকি "text-এর একটা character খেয়ে block ধরে রাখি (i-1, একই j)?" এই দুই-শাখায় ভাঙলে ভীতিকর regex-ও সাধারণ string DP হয়ে যায়।

ছবিতে বোঝা

s = "aa", p = "a*"। Row = s-প্রান্ত, column = p-প্রান্ত (T/F):

উদাহরণ
          ""    a     *
   ""     T     F     T
   a      F     T     T
   a      F     F     T   <- answer

rule:
  p[j-1] != '*':  dp[i][j] = dp[i-1][j-1] and (p[j-1]==s[i-1] or p[j-1]=='.')
  p[j-1] == '*':  dp[i][j] = dp[i][j-2]                       # zero বার
                            or ( (p[j-2]==s[i-1] or p[j-2]=='.')
                                 and dp[i-1][j] )             # one+ বার

dp[0][2]=T কারণ a* শূন্য a দিয়ে খালি string-এ মেলে; শেষে dp[2][2]=T মানে "aa" মেলে "a*"-এর সাথে।

ছোট input-এ ধাপে ধাপে

s = "ab", p = ".*", table (rows = s, cols = p):

  1. base: dp[0][0]=T; dp[0][1] ('.', * নয়) = dp[-][-1]... → F; dp[0][2] ('*') = dp[0][0] = T
  2. i=1 (s[0]='a'): j=1 ('.') → dp[0][0] and ('.'=='.') = T; j=2 ('*', জোড়া . *): dp[1][0]=F; '.' মেলে 'a' → or dp[0][2]=T → T
  3. i=2 (s[1]='b'): j=1 ('.') → dp[1][0]=F; j=2 ('*'): dp[2][0]=F; '.' মেলে 'b' → or dp[1][2]=T → T
  4. dp[2][2] = T → answer

হাতে মিলিয়ে: .* যেকোনো string-এর সাথে মেলে, তাই "ab" মেলে — True. ✔

কোড ও ব্যাখ্যা

Python

Python
# ---- way 1: memoization (top-down) ----
def is_match_memo(s, p):
    from functools import lru_cache
    @lru_cache(maxsize=None)
    def solve(i, j):                         # s[i:] vs p[j:]
        if j == len(p):
            return i == len(s)
        first = i < len(s) and (p[j] == s[i] or p[j] == '.')
        if j + 1 < len(p) and p[j + 1] == '*':
            return solve(i, j + 2) or (first and solve(i + 1, j))
        return first and solve(i + 1, j + 1)
    return solve(0, 0)

# ---- way 2: tabulation (bottom-up, 2D boolean) ----
def is_match_tab(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for j in range(1, n + 1):                # খালি s-এ pattern মেলে?
        if p[j - 1] == '*' and j >= 2:
            dp[0][j] = dp[0][j - 2]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] != '*':
                dp[i][j] = dp[i - 1][j - 1] and (p[j - 1] == s[i - 1] or p[j - 1] == '.')
            else:
                dp[i][j] = dp[i][j - 2]                       # zero বার
                if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                    dp[i][j] = dp[i][j] or dp[i - 1][j]      # one+ বার
    return dp[m][n]

# ---- tests ----
cases = [
    ("aa", "a", False),
    ("aa", "a*", True),
    ("ab", ".*", True),
    ("aab", "c*a*b", True),
    ("mississippi", "mis*is*p*.", False),
    ("", "", True),
    ("", "a*", True),
    ("a", "", False),
    ("ab", ".*c", False),
    ("aaa", "a*a", True),
]
for s, p, want in cases:
    assert is_match_memo(s, p) == want, (s, p, is_match_memo(s, p))
    assert is_match_tab(s, p) == want, (s, p, is_match_tab(s, p))

print("সব test pass!")

কোডের প্রতিটি অংশ

  • is_match_memo: solve(i, j) দুই suffix মেলে কি না; pattern শেষ হলে text-ও শেষ হতে হবে; first চলতি character মেলে কি না; পরের character * হলে দুই শাখা (skip jodi / consume one), নয়তো সাধারণ এক-character; lru_cache repeat এড়ায়।
  • is_match_tab: dp[0][0]=True; প্রথম row-এ শুধু x* জোড়া খালি string-এ মেলে; nested loop-এ *-নয় হলে diagonal+match, * হলে j-2 (zero) OR i-1 (one+); answer dp[m][n]।

Output মিলিয়ে দেখা

cases-এ দশটা input: classic LeetCode উদাহরণগুলো ("aa"/"a" False, "aa"/"a*" True, "ab"/".*" True, "aab"/"c*a*b" True, "mississippi"/... False), দুই খালি-string edge, "a"/"" False, একটা trailing-mismatch "ab"/".*c" False, আর "aaa"/"a*a" True (overlap)। প্রতিটার জন্য দুই function-ই একই boolean দিতে হবে। সব pass হলে শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল

সময়

দুই version-ই O(m·n) — প্রতিটা (i, j) জোড়া একবার গোনা হয়, transition O(1)। (Naive recursion ছিল exponential।)

অতিরিক্ত জায়গা

  • Memoization: O(m·n) cache + recursion stack।
  • Tabulation: O(m·n) — boolean table (দুই rolling row-এ O(n)-এও করা যায়)।

যে ভুলগুলো এড়াতে হবে

  • *-কে একা একটা character ভাবা — এটা সবসময় ঠিক আগের character-এর সাথে জোড়া; তাই pattern-এ * কখনো index 0-তে একা আসে না, আর j-2-এ লাফ দিতে হয়।
  • dp[0][j] base row ভুল করা — a*b* জাতীয় pattern খালি string-এ মেলে, এটা dp[0][j]=dp[0][j-2] দিয়ে না বসালে valid match মিস হয়।
  • "one+" শাখায় match-check ভুলে শুধু dp[i-1][j] নেওয়া — আগের pattern-character s[i-1]-এর সাথে আগে মিলতে হবে, নয়তো ভুল True।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: #17 LCS ও #18 Edit Distance-এর two-prefix grid; ../patterns.md-এর "String DP" family-তে wildcard matching-কে এই grid-skeleton-এর সদস্য বলা হয়েছে। নতুন শুধু *-এর দুই-শাখা transition।

পরের অনুশীলন

কৌশলটি মনে রাখুন

String DP with * block: two-prefix dp[i][j], কিন্তু * একটা "শূন্য-বা-বেশি" block বানায় — দুই শাখা: block বাদ (j-2) বা text-character খেয়ে block ধরে রাখা (i-1)। এই দুই-শাখা reframing wildcard/regex-ধাঁচের সব matching DP-তে ফেরে।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "Regex Matching = LCS-grid + * দুই-শাখা।" State dp[i][j] = s-এর প্রথম i ও p-এর প্রথম j মেলে কি না, * না হলে diagonal+match, * হলে dp[i][j-2] OR (match হলে) dp[i-1][j], base row সাবধানে। মনে রেখো: *-কে আগের character-এর সাথে জোড়া "block" ভাবলেই ভয়টা চলে যায়।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।