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 as:

dp = []

for _ in (0...s.length() + 1)  
  dp.push([false] * (p1.length() + 1))
end

The element dp[i][j] is used to represent if the string s[0..i] and p1[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 p1 or both being empty strings. This is why it has a size of (|s|+1) * (|p1|+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 p1 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 p1[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

...