022 — Regular Expression Matching¶

Source¶

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-এর * একটা চতুর "শূন্য বা একাধিক" শাখা যোগ করে

1. Problem in simple words¶

একটা 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

2. Which basic idea does this inherit from?¶

ভিত্তি #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" বানায়।

3. What is the hidden math or logic?¶

লুকানো 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।

4. Which data structure is needed?¶

একটা 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-এ মেলে"।

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

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*"-এর সাথে।

8. Example input and 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

9. Brute force thinking¶

প্রথম সরল চিন্তা: 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)

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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।

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

base: dp[0][0]=T; dp[0][1] ('.', * নয়) = dp[-][-1]... → F; dp[0][2] ('*') = dp[0][0] = T
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
i=2 (s[1]='b'): j=1 ('.') → dp[1][0]=F; j=2 ('*'): dp[2][0]=F; '.' মেলে 'b' → or dp[1][2]=T → T
dp[2][2] = T → answer

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

15. Python solution¶

# ---- 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!")

16. Line-by-line code explanation¶

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]।

17. Output walkthrough¶

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!।

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

*-কে একা একটা 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।

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

Wildcard Matching (? আর * যেখানে * যেকোনো sequence) — https://leetcode.com/problems/wildcard-matching/
Distinct Subsequences (count, two-prefix grid) — https://leetcode.com/problems/distinct-subsequences/
Interleaving String (দুই source এক target) — https://leetcode.com/problems/interleaving-string/

23. Pattern learned¶

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

24. Final summary¶

ভবিষ্যতের আমাকে: "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।