# 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.