Mastering Regular Expression Matching for Coding Interviews
Written on
Chapter 1: Understanding Regular Expression Matching
Regular expression matching can often pose a challenging problem in coding interviews. The task involves taking an input string s and a pattern p, and implementing a solution that supports the special characters . and *. Here, . can represent any single character, while * signifies zero or more instances of the preceding character. The aim is to ensure that the entire input string matches the given pattern.
For instance, consider the following examples:
- Example 1:
- Input: s = "aa", p = "a"
- Output: false
- Explanation: The pattern "a" does not cover the entire string "aa".
- Example 2:
- Input: s = "aa", p = "a*"
- Output: true
- Explanation: The * allows for zero or more occurrences of 'a', thus matching "aa".
- Example 3:
- Input: s = "ab", p = ".*"
- Output: true
- Explanation: The pattern .* indicates that any character can occur zero or more times.
Constraints:
- 1 <= s.length <= 20
- 1 <= p.length <= 30
- The string s consists solely of lowercase English letters.
- The pattern p also consists of lowercase letters, alongside . and *.
Optimized Approach
Given that the problem has an optimal substructure, it is beneficial to cache intermediate results. We can frame the question as dp(i, j): do the substrings text[i:] and pattern[j:] match? Our solution can be derived from previous answers related to smaller substrings.
Here is a solution implemented in Python:
class Solution(object):
def isMatch(self, text, pattern):
memo = {}
def dp(i, j):
if (i, j) not in memo:
if j == len(pattern):
ans = i == len(text)else:
first_match = i < len(text) and pattern[j] in {text[i], '.'}
if j + 1 < len(pattern) and pattern[j + 1] == '*':
ans = dp(i, j + 2) or (first_match and dp(i + 1, j))else:
ans = first_match and dp(i + 1, j + 1)memo[i, j] = ans
return memo[i, j]
return dp(0, 0)
C++ Solution:
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 2] || (i && dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));} else {
dp[i][j] = i && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');}
}
}
return dp[m][n];
}
};
Java Solution:
enum Result {
TRUE, FALSE
}
class Solution {
Result[][] memo;
public boolean isMatch(String text, String pattern) {
memo = new Result[text.length() + 1][pattern.length() + 1];
return dp(0, 0, text, pattern);
}
public boolean dp(int i, int j, String text, String pattern) {
if (memo[i][j] != null) {
return memo[i][j] == Result.TRUE;}
boolean ans;
if (j == pattern.length()) {
ans = i == text.length();} else {
boolean first_match = (i < text.length() && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
ans = (dp(i, j + 2, text, pattern) || (first_match && dp(i + 1, j, text, pattern)));} else {
ans = first_match && dp(i + 1, j + 1, text, pattern);}
}
memo[i][j] = ans ? Result.TRUE : Result.FALSE;
return ans;
}
}
Stay tuned for more intriguing interview questions that will help you sharpen your coding skills!
Chapter 2: Video Tutorials on Regular Expression Matching
To further enhance your understanding of regular expression matching, check out the following videos:
This video covers dynamic programming techniques for regular expression matching, specifically using top-down memoization approaches.
In this tutorial, a code walkthrough is presented alongside whiteboard explanations for regular expression matching, especially focusing on the Leetcode problem.