Pattern visualizer

Regular Expression Matching

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. 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?.