0010. Regular Expression Matching

Step-by-step DP table filling animation

← 0009. Palindrome Number
Bottom-up DP
Memoization
Space Optimized
Rules
Step: 0 / 0 Result: ...

DP Table: dp[i][j] = does s[:i] match p[:j]?

Play or Step to begin.
Current cell
Newly filled
Looked up
Answer

Memo Table: memo[i][j] = isMatch(s[i:], p[j:])

Play or Step to begin. Memo is filled via top-down recursion.
Current call
Retrieved from cache
True
False

Two rows: prev[] and curr[]

Play or Step to begin. Only 2 rows are used.

Regex Matching Rulesi

. — Matches any single character.

Example: a.c → "abc", "axc", "a1c" matches

* — Repeats the preceding element zero or more times.

Example: a* → "", "a", "aa", "aaa", ... matches

Example: .* → har qanday qatormatches (universal)

DP Transition Rulesi

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

1. Zero times: dp[i][j] = dp[i][j-2]

→ We completely skip the "x*" pair

2. One+ times: If s[i-1] == p[j-2] or p[j-2] == '.'

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

→ We "consume" one character from s, pattern stays

If s[i-1] == p[j-1] or p[j-1] == '.':

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

→ Characters match — take the diagonal value

Otherwise:

dp[i][j] = false

→ Characters do not match

Algorithm Complexity
Recursion
O(2^(m+n))
O(2^(m+n)) / O(m+n)
DP Bottom-Up
O(m·n)
O(m·n) / O(m·n)