Feature #9: File Search
Explore how to build a file search feature that matches file names using regular expressions with . and * characters. Learn a bottom-up dynamic programming method for complete string matching, understand the algorithm's structure, and analyze its time and space complexity.
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:
dp = [[False] * (len(p) + 1) for _ in range(len(s) + 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 len(s) * len(p) 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. ...