DSA Tracker

Visualize

Regular Expression Matching

A table where a star is two branches: erase the pair, or eat one more character

time O(m*n)space O(m*n)

A star is hard because it has no fixed width — it can cover nothing, or half the text. The table sidesteps that by never deciding how wide a star is: dp[i][j] only asks whether the first i characters of the text match the first j characters of the pattern, and a star gets exactly two ways to answer. Erase yourself, which skips two pattern characters and reads the cell two columns left. Or eat one text character, which is only legal when the character before the star matches, and reads the cell directly above — the same star, one character of text shorter. Everything else is the ordinary case: a matching character or a dot costs one from each side and reads the diagonal. The arrows are those three moves.

Details

Animated on: Does "aab" match the pattern "c*a*b", where "." stands for any single character and "*" means zero or more of the character before it?

Problem:Regular Expression MatchingHard

A table where a star is two branches: erase the pair, or eat one more character

step 1 / 14

dp[i][j]: do the first i characters of "aab" match the first j characters of "c*a*b"?

Text "aab" against pattern "c*a*b". Row 0 is the empty text, column 0 the empty pattern, and the answer is the bottom-right corner dp[3][5]. Every cell asks the same question about a shorter prefix of each.

Pseudocode
1FUNCTION isMatch(s, p)
2  dp[0][0] <- TRUE
3  FOR j FROM 1 TO LENGTH(p)
4    IF p[j-1] = '*'
5      dp[0][j] <- dp[0][j-2]
6  FOR i FROM 1 TO LENGTH(s)
7    FOR j FROM 1 TO LENGTH(p)
8      IF p[j-1] = '*'
9        dp[i][j] <- dp[i][j-2]
10        IF p[j-2] = s[i-1] OR p[j-2] = '.'
11          dp[i][j] <- dp[i][j] OR dp[i-1][j]
12      ELSE IF p[j-1] = s[i-1] OR p[j-1] = '.'
13        dp[i][j] <- dp[i-1][j-1]
14  RETURN dp[LENGTH(s)][LENGTH(p)]

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. Text "aab" against pattern "c*a*b". Row 0 is the empty text, column 0 the empty pattern, and the answer is the bottom-right corner dp[3][5]. Every cell asks the same question about a shorter prefix of each.
  2. Empty text against empty pattern: dp[0][0] = T. Nothing has to match nothing, and this single true cell is what every other answer is eventually traced back to.
  3. Column 1 is the pattern "c" alone. A plain character has to eat a text character and row 0 has none left, so dp[0][1] = F.
  4. "c*" can mean zero copies of "c", so it may vanish entirely. Skipping both pattern characters lands on dp[0][0] = T, and dp[0][2] inherits it: T.
  5. Same erasure again for "a*": drop the pair and read dp[0][2] = T. Two stars in a row can both disappear, so the empty text still matches "c*a*" — dp[0][4] = T.
  6. "b" is not a star, so it cannot be erased and there is no text for it to consume. dp[0][5] = F — the whole pattern needs at least one character of text.
  7. Now the text side grows. Column 0 is the empty pattern, and an empty pattern can never cover a non-empty text, so dp[1][0] = F and the rest of column 0 will be too.
  8. Text "a" against pattern "c": the characters differ and "c" is not a dot, so no rule applies at all and dp[1][1] stays F.
  9. "c*" has to erase itself here — "c" does not equal "a", so it cannot consume the "a". Only the skip branch is available: dp[1][0] = F carries over, dp[1][2] = F.
  10. The interesting case. "a*" can erase itself (dp[1][2] = F) or eat one "a" and ask whether the shorter text still matched (dp[0][4] = T). Either branch being true is enough, so dp[1][4] = T.
  11. A star reuses itself: dp[1][4] = T already matched one "a", so consuming a second one just points back up the same column. That is how "a*" stretches to "aa" — dp[2][4] = T.
  12. Row 3 ends in "b". Pattern character "a" does not match it, so dp[3][3] = F — "a" cannot be the thing that covers a "b".
  13. "a*" cannot eat the "b" either, so only the erase branch survives: dp[3][2] = F, hence dp[3][4] = F. The star has stopped growing, which is exactly what leaves the "b" for the last pattern character.
  14. The last "b" matches the last "b", so it hands the question back to dp[2][4] = T — the cell where "c*a*" had already swallowed "aa". dp[3][5] = T: "aab" matches "c*a*b".

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Regular Expression Matching in the editorAll Dynamic Programming problemsBack to roadmap