Implementing Regular Expression Matching

Given two strings S and P where S consists of only lowercase English alphabets while P consists of lowercase English alphabets as well as special characters ‘.’ and ‘*’, the task is to implement a function to test regular expression such that:

• '.' Matches any single character.​​​​
• '*' Matches zero or more of the preceding element.

Note: For each appearance of the character ‘*', there will be a previous valid character to match.

Examples:

Input: s = "aaa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aaa".

Input: s = "abb", p = "a.*"
Output: true
Explanation: replace . with b then p becomes ab* now replace * with one preceeding character hence p becomes abb.

Approach: To solve the problem follow the below observations:

• Suppose: s = “aa” and p = “aa”, since all the characters in both s and p are the same, it’s a match.
• Suppose:  s = “aabb” and p = “aab*”, We know that substrings bb and b* match because * can be replaced by one b. Since we already know that the remaining substrings “aa” and “aa” are matched, the whole strings are also a match.

What can we infer from this? Right, if we have a solution of part of a problem, we can use that partial result and can go forward. Also, we can use the already calculated result without calculating it again.

Does this ring a bell ????? Yes, this problem satisfies the following two properties –

• Optimal Substructure — Any problem has optimal substructure property if its overall optimal solution can be constructed from the optimal solutions of its subproblems.
• Overlapping Subproblems — Any problem has overlapping sub-problems if finding its solution involves solving the same subproblem multiple times.

It is now evident that we can use Dynamic Programming to solve this problem. Below are the steps —

• Create a boolean 2D dp array with sizes as boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]. We are adding extra 1 to incorporate the case in case either or both of the strings are empty.
• If both strings are empty, then it’s a match, thus, dp[0][0] = true.
• Let’s take an example s = "aab" and p = "c*a*b" and create a DP table.

• First column — it means p is empty and it will match to s only if s is also empty which we have stored in dp[0][0]. Thus, remaining values of dp[0][i] will be false.
• First row — this is not so easy. It means which p matches empty s. The answer is either an empty pattern or a pattern that represents an empty string such as "a*", "x*y*", "l*m*n*" and so on. In the above example, if s = "" and p = "c*", then due to *, c can be replaced by 0 cs which gives us an empty string. Hence, dp[0][2] = true.
• For non-empty strings, let’s say that s[i - 1] == p[j - 1] this means the (i – 1)^th and (j – 1)^th characters are same. This means, we have to check if the remaining strings are a match or not. If they are a match, then the current substrings will be a match, otherwise they won’t be a match i.e., dp[i][j] = dp[i - 1][j - 1]. We’re taking (i – 1)^th and (j – 1)^th characters to offset empty strings as we’re assuming our strings start from index 1.
• If p[j - 1] == ".", then it means any single character can be matched. Therefore, here also, we will have to check if the remaining string is a match or not. Thus, dp[i][j] = dp[i - 1][j - 1].
• If p[j - 1] == "*", then it means either it’s represents an empty string (0 characters), thus dp[i][j] = dp[i][j - 2] or s[i - 1] == p[j - 2] || p[j - 2] == ".", then current character of string equals the char preceding ‘*' in pattern so the result is dp[i-1][j].

Below is the implementation of above approach:

true

Time Complexity: O(m×n)
Auxiliary Space: O(m×n)