Feature #9: File Search

Description

In this feature, we will make a search files functionality using regular expressions. We will be provided with a list of files and a regular expression. We will have to implement regular expression matching and return all the file names that will match the regular expression. The feature must include support for . and * characters where:

• . can match any single character. ​​​​
• * can match zero or more of the preceding characters.

The matching should cover the input string entirely (not partially).

Let’s look at a few examples:

Solution

We will solve this problem using the bottom-up approach. First, we will initialize a 2D boolean array like this:

var dp = new bool[s.Length + 1, p.Length + 1];

The element dp[i][j] is used to represent if the string s[0..i] and p[0..j] match or not (true or false). This would mean that dp should be s.Length * p.Length in size. But, we’ll have a base case of either s or p or both being empty strings. This is why it has a size of (|s|+1) * (|p|+1).

All of the values in the array shown above will be initialized with false. We will set dp[0][0] = true because if both s and p are empty, then they must be the same.

Now, let’s go over the algorithm:

1. The first row represents an