Regular Expression Matching
Today, let’s focus on implementing a regular expression engine. Matching a given input string against a regular expression pattern is a very common application in the real world. Most regular expression engines are far too complex, and are often based on Finite automata state machines. However, our naive implementation doesn’t use Finite automata state machines. Regular Expression Matching - Problem Statement Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Regular Expression Matching - Definition For the input string $s$ and the pattern $p$, each with length $m$ and $n$ characters respectively, let $t[i][j]$ be the evaluation of the string $s_1 \ldots s_i$ against the pattern $p_1 \ldots p_j$ such that $0 \le i \le m$ and $0 \le j \le n$. H