Regular Expression Matching Editorial

Practice Problem Link: Regular Expression Matching

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Implement regular expression matching.

In a regular expression:

• a-z matches the corresponding character.
• . matches any single character.
• * matches zero or more of the preceding character.

The entire input string should be matched.

The function would take a string s and the regular expression pattern p.

Naive Approach

The naive approach is to use a brute force recursion-based approach. The recurrence is that if there were no Wildcard Characters, we can simply iterate on the string and check if the strings match or not. Else if there is a wildcard character, we will have to check all the possible suffixes of the text and check if they match with the pattern or not, all of which can be simply implemented using a brute force recursion based solution.

Analysis

• Time Complexity: Exponential
• Space Complexity: Exponential

Implementation

C++

bool isMatch (string s, string p) {
    if(p.empty()) {
		return s.empty();
	}
	bool match = true;
	if(s.empty() || (p[0] != s[0] && p[0] != '.')) {
		match = false;
	}
	if(p.size() == 1 || p[1] != '*') {
		return match && isMatch(s.substr(1), p.substr(1));
	} else {
		if(isMatch(s, p.substr(2))) {
			return true;
		} else {
			return (match && isMatch(s.substr(1), p));
		}
	}
}

Java

class Solution {
	boolean isMatch (String s, String p) {
	    if(p.length() == 0) {
			return s.length() == 0;
		}
		boolean match = true;
		if(s.length() == 0 || (p.charAt(0) != s.charAt(0) && p.charAt(0) != '.')) {
			match = false;
		}
		if(p.length() == 1 || p.charAt(1) != '*') {
			return match && isMatch(s.substring(1), p.substring(1));
		} else {
			if(isMatch(s, p.substring(2))) {
				return true;
			} else {
				return (match && isMatch(s.substring(1), p));
			}
		}
	}
}

Optimal Approach

We can observe in our naive solution that multiple function calls are getting repeated again and again. This gives us the idea to memoize these function calls to prevent them from getting repeated again and again. So, we use DP to memoize these function calls and solve the problem in polynomial time complexity.

Analysis

• Time Complexity: O(|s| + |p|)
• Space Complexity: O(|s| + |p|)

Implementation (Recursive)

C++

vector<vector<int>> dp;
bool solve(string s, string p) {
	if(p.empty()) {
		return s.empty();
	}
	bool match = true;
	if(s.empty() || (p[0] != s[0] && p[0] != '.')) {
		match = false;
	}
	if(dp[s.length()][p.length()] != -1) {
		return dp[s.length()][p.length()];
	}
	if(p.size() == 1 || p[1] != '*') {
		return  dp[s.length()][p.length()] = match && solve(s.substr(1), p.substr(1));
	} else {
		if(solve(s, p.substr(2))) {
			return true;
		} else {
			return dp[s.length()][p.length()] = (match && solve(s.substr(1), p));
		}
	}
}
bool isMatch (string s, string p) {
    dp.assign(s.length() + 1, vector<int> (p.length() + 1, -1));
	return solve(s, p);
}

Java

class Solution {
	Boolean dp[][];
	boolean solve(String s, String p) {
		if(p.length() == 0) {
			return s.length() == 0;
		}
		boolean match = true;
		if(s.length() == 0 || (p.charAt(0) != s.charAt(0) && p.charAt(0) != '.')) {
			match = false;
		}
		if(dp[s.length()][p.length()] != null) {
			return dp[s.length()][p.length()];
		}
		if(p.length() == 1 || p.charAt(1) != '*') {
			return  dp[s.length()][p.length()] = match && solve(s.substring(1), p.substring(1));
		} else {
			if(solve(s, p.substring(2))) {
				return true;
			} else {
				return dp[s.length()][p.length()] = (match && solve(s.substring(1), p));
			}
		}
	}
	boolean isMatch (String s, String p) {
	    dp = new Boolean[s.length() + 1][p.length() + 1];
		return solve(s, p);
	}
}

Implementation(Iterative)

C++

bool isMatch (string s, string p) {
    int n = s.size(), m = p.size();
	int dp[n + 1][m + 1];
	for(int i = 0; i <= n; i++) {
		dp[i][0] = 0;
	}
	dp[0][0] = 1;
	for(int i = 0; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			dp[i][j] = 0;
			if(p[j - 1] == '*') {
				if(j >= 2) {
					dp[i][j] |= dp[i][j - 2];
				}
				dp[i][j] |= (i && dp[i - 1][j] && j >= 2 && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
			}
			else{
				if(p[j - 1] == '.' && i) {
					dp[i][j] = dp[i - 1][j - 1];
				}
				else{
					if(i && s[i - 1] == p[j - 1]) {
						dp[i][j] = dp[i - 1][j - 1];
					}
					else {
						dp[i][j] = 0;
					}
				}
			}
		}
	}
	return dp[n][m];
}

Java

class Solution {
	boolean isMatch (String s, String p) {
		boolean dp[][] = new boolean[s.length() + 1][p.length() + 1];
        for(int i = 0; i <= s.length(); i++){
            for(int j = 0; j <= p.length(); j++){
                if(j == 0 && j == i) {
                    dp[i][j] = true;
				}
                else if(j == 0) {
                    dp[i][j] = false;
				}
                else if(i == 0 && p.charAt(j - 1) != '*') {
                    dp[i][j] = false;
				}
                else if(i == 0) {
                     dp[i][j] = dp[i][j - 2];
				}
                else {
                    if(p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                    if(p.charAt(j - 1) == '*'){
                        dp[i][j] = dp[i][j - 2];
						boolean match = ((p.charAt(j - 2) == '.' ||  p.charAt(j - 2) == s.charAt(i - 1)) && dp[i - 1][j]);
						dp[i][j] = dp[i][j] || match;
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
	}
}