Regular Expression Matching
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Does pattern p match the whole string s? '.' matches any single letter; 'x*' matches zero or more of x.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Can "a*" match the empty string? What about "a*b*"?
- Hint 2For a '*', consider two options: use it zero times, or use it once more.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A rubber stamp. A pattern like "c*a*b" is a row of stamps where "c*" means: press the c-stamp as many times as you like, even none. To check whether the string is stampable, fill a table of "can the first a letters of the string be produced by the first b symbols of the pattern?". A star symbol can either be pressed zero times (look two pattern symbols back) or one more time if the current letter matches (look one string letter back).
- The obvious way
Recursive matching with branching on every '*' is exponential without memory.
- The key insight
match[a][b] = first a letters of s match first b symbols of p. match[0][0] = True. If p[b - 1] is '*': match[a][b] = match[a][b - 2] (zero times) or (a > 0 and the letter s[a - 1] fits p[b - 2] and match[a - 1][b]). Otherwise match[a][b] = a > 0 and the letter fits p[b - 1] and match[a - 1][b - 1]. A letter fits if the symbol is '.' or equal.
- The algorithm
- match[0][0] = True; the star can erase its letter: match[0][b] = match[0][b - 2].
- For a normal symbol: letter fits and the diagonal is True.
- For '*': zero times (two symbols back) or one more (cell above, if the letter fits).
- Return the bottom-right cell.
Watch it run
Examples = "aab", p = "c*a*b"
"c*" can be pressed zero times, so the pattern "c*a*b" starts like "a*b".
c* = zero
Where people slip
- '*' never appears first; it always modifies the symbol before it.
- Match the WHOLE string, not just a part of it.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def is_match(s, p):
match = [[False] * (len(p) + 1) for _ in range(len(s) + 1)] # first a letters vs first b symbols
match[0][0] = True
for symbols in range(2, len(p) + 1):
if p[symbols - 1] == "*":
match[0][symbols] = match[0][symbols - 2] # "x*" can stamp zero times
def fits(letter_position, symbol_position): # does the symbol accept the letter?
return p[symbol_position] == "." or p[symbol_position] == s[letter_position]
for letters in range(1, len(s) + 1):
for symbols in range(1, len(p) + 1):
if p[symbols - 1] == "*":
zero_times = match[letters][symbols - 2]
one_more = fits(letters - 1, symbols - 2) and match[letters - 1][symbols]
match[letters][symbols] = zero_times or one_more
else:
match[letters][symbols] = fits(letters - 1, symbols - 1) and match[letters - 1][symbols - 1]
return match[len(s)][len(p)]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.