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:

boolean[][] dp = new boolean[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 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). Similarly, we ...