Regular Expression Matching

Piggy-backing on the conceptual work of Edit Distance, we have a more challenging problem called Regular Expression Matching. The problem is this: given an input string s and a pattern p, you must return whether p matches s entirely. If you aren't familiar with regex, this problem uses a simplified system with only two properties: . which is a placeholder character, and * which is a character that expands the previous character 0 or more times. For example, a* matches on "", "a", "aa", and so on.

Lets just think about how this problem may go in our heads, specifically with this * operator. How should the program know when to stop "consuming" characters, or when to make the best decision? Well, it should be clear that this is a 2D DP approachEspecially since I talked about Edit Distance above because if we were to backtrack on every possibility we would get a massive search space and timeout. So lets dive into the implementation.

As with any DP problem, we immediately want to think about what we want to start to fill in with our bottom-up approach before we start the main iterations. This provides a sort of structure that our later states can pull from so that we can achieve an accurate answer. The base case here is kind of hard to see in terms of implementation, but intuitively it makes sense. The idea is we want to determine the substrings that match on an empty input string. With regex, this means that every character has a * after it. For example, a*b*c* matches to "". However, aa*b*c* requires an a, so it doesn't match the empty string. From the implementations perspective, this means that every other character is * and thus:

dp[0][0] = True
for i in range(2,n):
	dp[0][i] == dp[0][i-2]

Now what about the general case? This is where it really starts to piggy back on Edit Distance. If you think about it, this problem is essentially just Edit Distance with the inclusion of the * operator, since you know that . always matches. This helps us make an important decision, we categorize each iteration of our inner loop as either being a character with * or not.

for i in range(1,len(s) + 1):
	for j in range(1,len(p) + 1):
		if p[j-1] == "*":
			...
		else:
			...

The else case here is simple, so we'll start with that. In the current state, dp[i][j] should be True if the previous substring matched and the current character is either a match or p's character is ..

if p[j-1] == s[i-1] or p[j-1] == ".":
	dp[i][j] = dp[i-1][j-1]

Now for the case where p[j-1] == "*", we see something very similar. In fact, we essentially repeat the logic above, but with an extra step and some different indexing. First, and similarly to what we did for the base case, what if the * allows us to match to an empty string? In that case, we could do dp[i][j] = dp[i][j-2], since if we can just get rid of the regex'd character, then why not? The next step is very similar to the else case above. However, you are looking back one index further, so the condition becomes

if p[j-2] == s[i-1] or p[j-2] == ".":

But what is the recurrence relation? If we were to just match it to the value of dp[i-1][j-1], what does this really mean? Well it effectively ignores the * operator's main functionality: matching all of the characters!. Envision the 2D grid in your head, going down the same column that has the asterisk. You should be able to match as many characters against the * with this trick! And thats it! Here is the completed solution

def isMatch(self, s: str, p: str) -> bool:
	n = len(s)
	m = len(p)
	dp = [[False]* (m+1) for _ in range(n+1)]
	
	# "" and ""
	dp[0][0] = True
		
	# Match all patterns for empty substring
	for i in range(2,m+1):
		if p[i-1] == "*":
			dp[0][i] = dp[0][i-2]

	for i in range(1,n+1):	
		for j in range(1,m+1):
			if p[j-1] == "*":
				# Glob gets eliminated
				dp[i][j] = dp[i][j-2]
				if p[j-2] == s[i-1] or p[j-2] == ".":
					dp[i][j] |= dp[i-1][j]
			else:
				# Basic sequence, character matches
				if p[j-1] == s[i-1] or p[j-1] == ".":
					dp[i][j] = dp[i-1][j-1]

return dp[n][m]