Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Regular Expression Matching
Bookmark
Recursion
Memoization
Bottom-Up DP
Input
Star match
Dot star
Complex
Long (no match)
Repeated stars (cache hits)
Custom
s
=
aa
,
p
=
a*
s =
"aa"
p =
"a*"
.
any,
x*
zero or more
pattern (j)
s (i)
0
1
2
a
*
∅
0
1
2
a
a
∅
F
F
F
F
F
F
F
F
F
does "aa" match the regex "a*"? whole string, x* binds to the char before it
s =
"aa"
p =
"a*"
.
any,
x*
zero or more
pattern (j)
s (i)
0
1
2
a
*
∅
0
1
2
a
a
∅
F
F
F
F
F
F
F
F
F
does "aa" match the regex "a*"? whole string, x* binds to the char before it
s =
"aa"
p =
"a*"
.
any,
x*
zero or more
pattern (j)
s (i)
0
1
2
a
*
∅
0
1
2
a
a
∅
F
F
F
F
F
F
F
F
T
dp[2][2]
=
T
empty suffix matches empty pattern, fill from here
s =
"aa"
p =
"a*"
.
any,
x*
zero or more
pattern (j)
s (i)
0
1
2
a
*
∅
0
1
2
a
a
∅
F
F
F
F
F
F
T
F
T
0x
"a*"
can vanish: dp[2][0] = dp[2][2] =
T
s =
"aa"
p =
"a*"
.
any,
x*
zero or more
pattern (j)
s (i)
0
1
2
a
*
∅
0
1
2
a
a
∅
F
F
F
F
F
F
T
F
T
s[
1
] =
'a'
vs p[
1
] =
'*'
: firstMatch =
F
s =
"aa"
p =
"a*"
.
any,
x*
zero or more
pattern (j)
s (i)
0
1
2
a
*
∅
0
1
2
a
a
∅
F
F
F
F
F
F
T
F
T
'a' != '*'
no star to save it: dp[1][1] =
F
s =
"aa"
p =
"a*"
.
any,
x*
zero or more
pattern (j)
s (i)
0
1
2
a
*
∅
0
1
2
a
a
∅
F
F
F
T
F
F
T
F
T
0x
"a*"
:
vanish F
or
consume 'a' T
=
T
s =
"aa"
p =
"a*"
.
any,
x*
zero or more
pattern (j)
s (i)
0
1
2
a
*
∅
0
1
2
a
a
∅
F
F
F
T
F
F
T
F
T
s[
0
] =
'a'
vs p[
1
] =
'*'
: firstMatch =
F
s =
"aa"
p =
"a*"
.
any,
x*
zero or more
pattern (j)
s (i)
0
1
2
a
*
∅
0
1
2
a
a
∅
F
F
F
T
F
F
T
F
T
'a' != '*'
no star to save it: dp[0][1] =
F
s =
"aa"
p =
"a*"
.
any,
x*
zero or more
pattern (j)
s (i)
0
1
2
a
*
∅
0
1
2
a
a
∅
T
F
F
T
F
F
T
F
T
0x
"a*"
:
vanish F
or
consume 'a' T
=
T
s =
"aa"
p =
"a*"
.
any,
x*
zero or more
pattern (j)
s (i)
0
1
2
a
*
∅
0
1
2
a
a
∅
T
F
F
T
F
F
T
F
T
"aa" matches
"a*"
algo
master
.
io
Step:
Does "aa" match the regex "a*"? (. = any char, x* = zero or more x)
0 / 12
Input
Star match
Dot star
Complex
Long (no match)
Repeated stars (cache hits)
Custom
s
=
aa
,
p
=
a*
0 / 12
algo
master
.
io
Step:
Does "aa" match the regex "a*"? (. = any char, x* = zero or more x)
