Feature #9: File Search
Implementing the "File Search" feature for our "Operating System" project.
We'll cover the following...
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:
val dp = Array.ofDim[Boolean](text.length + 1, pattern.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:
- The