Coder's Cat

2019-12-02

## Question

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

Note:

Example 1:

Input:

## Explanation

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:

### Dynamic programming

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)$