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:

std::vector<std::vector<bool>> dp(m + 1, std::vector<bool>(n + 1, false));

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 empty string matched against variable substrings of the pattern. dp[0][1] will be true only if p[0] is *, which means that there were zero or more occurrences of the previous character. An empty string is zero occurrences of the previous character (being no character at all).

...