Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.
The matching should cover the entire input string (not partial).
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
This problem is not easy, some corner test cases need to handle carefully.
Please try to write the correct code first and then simplify it.
Depth-first search (DFS)
Let’s compare the current character of input and pattern.
There are two normal cases without consideration of
Now let’s consider how to handle the pattern
If we have a
X* in the pattern(X stands for any character), we can skip zero or more than one character(same as the previous one) from the input.
According to these analyses, we can construct a depth-first search algorithm, it’s a recursive algorithm.
This solution is slow, from the result we can see it only beat 11% submissions. The time complexity is hard to analyze. You may refer to more details here.
DFS with memorization
In the recursive version, there are some overlap subproblems we can optimize.
Naive DFS algorithm could be optimized with a memorization data structure. We could add a
memo map to store the computed result, it’s a typical caching technology.
In this solution, I use
text + "_" + pattern as a key for memorization, which is not the best.
The result is much better:
Since we could implement the algorithm in a top-down pattern, we could also implement it from bottom to up.
Here is the scenario where the dynamic programming techniques could be applied to.
The time complexity is $O(N*M)$