10. Regular Expression Matching

Difficulty Level : Hard

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

'.' Matches any single character.​​​​
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

 

Example 1:

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

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
 

Constraints:

1 <= s.length <= 20
1 <= p.length <= 20
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and '*'.
It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Solution

I had a significant misunderstanding about regular expressions until now. Because of this, I couldn’t solve the problem at all. When there is a regular expression like ‘a’, I thought that ‘a’ must appear, and ‘’ meant that the preceding ‘a’ appears 0 or n times to satisfy the expression. However, that’s not the case. ’a’ should be viewed as a single set. In other words, ‘a’ can also represent an empty string where ‘a’ does not appear even once. Therefore, an empty string is an example that satisfies the ‘a*’ regular expression.
To solve a problem using dynamic programming (DP), it’s crucial to verify whether the problem can be broken down into subproblems, i.e., whether it has a fractal structure. If it does, the problem can be solved using either a top-down or bottom-up approach. Generally, using a bottom-up approach is essential to meet time complexity requirements. All subproblems must be stored in the DP table to solve the higher-level problem efficiently.

#include <string>
#include <vector>

class Solution{
public:
	bool isMatch(string s, string p){
    	int m = s.size();
        int n = p.size();
        
        vector< vector<bool> > dp(m+1, vector<bool> (n+1, 0));
        
        dp[0][0] = 1; // empty string matching
        
        for(int i=1;i<n+1;i++)
        {
        	if(p[i-1] == '*')
            {
            	dp[0][i] = dp[0][i-2]; // 'a*' can be empty string. 
            }
        }
        
        for(int i=1;i<=m;i++)
        {
        	for(int j=1;j<=n;j++)
            {
            	if(p[j-1] == '.' || s[i-1] == p[j-1])
                {
                	dp[i][j] = dp[i-1][j-1]; 
                }
                else if(p[j-1] == '*')
                {
                	dp[i][j] = dp[i][j-2];
                    if(p[j-2] == '.' || s[i-1] == p[j-2]) // guaranteed the precedent character before '*' by the problem. So, j-2 is safe.
                    {
                    	dp[i][j] = dp[i][j] || dp[i-1][j];
                    }
                }
                else // different character. Already initialized by false. We can skip this else expression.
                {
                
                }
            }
        }
    }
}