Problem

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

Examples

Some examples:

isMatch("aa","a") ? false
isMatch("aa","a.") ? true
isMatch("aaa","ab*") ? false
isMatch("aa", ".*") ? true
isMatch("aa", "a*") ? true
isMatch("ab", ".*") ? true
isMatch("aabaa", "a*b.*") ? false

Note * doesnt match any element, but any preceding element multiple number of times.

Similar Problem

Wildcard Matching Problem. See the diff - Wildcard Matching Problem#Leetcode 44 Vs Leetcode 10 OR Regular Expression Matching Problem

Solution

Matching ‘.’ is straightforward : it will match any character at the current position. So, if the pattern starts with ‘.’ then it has to match any character in string. Other wise if pattern starts with a character other than '*' then it has to match the same character in the string. We can continue doing this if until we see a '*'.

If pattern contains a character followed by '*' then the pattern matches the starting character zero or more times. First, we can match zero length which is equivalent to not matching the first two character. If zero match doesn’t go through then we need to match all possible length suffix of string (why?) to match the pattern recursively.

Method 1 - Recursive Solution

The function recursively explores two main cases:

  • If pattern p ends with *: We can either match zero characters of the preceding element or match one or more characters (explored in a loop).
  • Otherwise, if the current characters match (including ‘.’ for any character), we proceed to the next characters in both strings.

The function checks if the pattern matches the string by considering whether the current characters match or if a * can be used to match zero or more characters. Now, in recursion we have cases:

  • Base Case: When the pattern is exhausted, the string should also be exhausted.
  • Recursive Case: Check if the next character of the pattern is *.
    • If yes, either skip over * or match one character and proceed recursively.
    • If no, check the current characters and proceed to the next characters.

Code

Java
public class Solution {

	public boolean isMatch(String s, String p) {
		return helper(s, p, 0, 0);
	}

	private boolean helper(String s, String p, int i, int j) {
		if (j == p.length()) {
			return i == s.length();
		}

		boolean firstMatch = (i < s.length() &&
			(p.charAt(j) == s.charAt(i) || p.charAt(j) == '.'));

		if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
			return (helper(s, p, i, j + 2) ||
				(firstMatch && helper(s, p, i + 1, j)));
		} else {
			return firstMatch && helper(s, p, i + 1, j + 1);
		}
	}
}

Complexity

  • ⏰ Time complexity: O(2^(m + n)), where m is length of s and n is length of p
    • In the worst case, the number of function calls could be exponential because each call potentially branches into two further calls when handling the '*' character.
  • 🧺 Space complexity: O(m + n), in worst case due to recursion stack

Method 2 - Top Down DP with Memoization

Code

Java
public class Solution {

	public boolean isMatch(String s, String p) {
		Map<String, Boolean> memo = new HashMap<>();
		return isMatchHelper(s, p, 0, 0, memo);
	}

	private boolean isMatchHelper(String s, String p, int i, int j, Map<String, Boolean> memo) {
		String key = i + "," + j;

		if (memo.containsKey(key)) {
			return memo.get(key);
		}

		if (j == p.length()) {
			return i == s.length();
		}

		boolean firstMatch = (i < s.length() &&
			(p.charAt(j) == s.charAt(i) || p.charAt(j) == '.'));

		boolean result;

		if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
			result = (isMatchHelper(s, p, i, j + 2, memo) ||
				(firstMatch && isMatchHelper(s, p, i + 1, j, memo)));
		} else {
			result = firstMatch && isMatchHelper(s, p, i + 1, j + 1, memo);
		}

		memo.put(key, result);
		return result;
	}
}

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(m*n) - O(m*n) for memo table, O(m + n) for recursion stack. O(m*n + m + n) = O(m * (n + 1 + n / m) ⇨ O(m*n)

Method 3 - Bottom Up DP

Trying to come up with code

public boolean isMatchDP(String s, String p) {
	if (s == null || p == null) {
		return false;
	}
	int m = s.length();
	int n = p.length();

	boolean[][] dp = new boolean[m + 1][n + 1];
Base Case 1
	dp[0][0] = true;  // if both pattern and string are empty: match
Base Case 2 - Handle Empty String

Kind of column initialization

	// dp[i][0] = false(which is default value of the boolean array) since empty pattern cannot match non-empty string
	// dp[0][i] matches string of length 0, i.e. "". Empty string can match each character in pattern where * exists and previous character matches
	// It should be #*#*#*#*..., or (#*)* if allow me to represent regex using regex
	for (int j = 1; j <= m; j++) {
		if (p.charAt(j) == '*') {
			dp[0][j] = dp[0][j - 1];
		}
	}

Handling the case when

DP Case
1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*':
DP Case Having *
   here are two sub conditions:
1  if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
			  dp[i][j] = dp[i-1][j]    //in this case, a* counts as multiple a 
		   or dp[i][j] = dp[i][j - 1]   // if p.charAt(j - 1) is counted as empty
		   or dp[i][j] = dp[i][j-2] // if counted as one

Code

Java
public class Solution {

	public boolean isMatch(String s, String p) {
		int m = s.length();
		int n = p.length();
		boolean[][] dp = new boolean[m + 1][n + 1];

		// dp[0][0] means both empty s and p matches
		dp[0][0] = true;

		// Fill the dp array
		for (int i = 0; i <= m; i++) {
			for (int j = 1; j <= n; j++) {

				if (p.charAt(j - 1) == '*') {
					// Star can match zero preceding elements
					dp[i][j] = dp[i][j - 2];

					if (i > 0 && (p.charAt(j - 2) == s.charAt(i - 1) ||
							p.charAt(j - 2) == '.')) {
						// Star can match one or more preceding elements
						dp[i][j] = dp[i][j] || dp[i - 1][j];
					}
				} else {
					if (i > 0 && (p.charAt(j - 1) == s.charAt(i - 1) ||
							p.charAt(j - 1) == '.')) {
						dp[i][j] = dp[i - 1][j - 1];
					}
				}
			}
		}

		return dp[m][n];
	}
}

Complexity

  • ⏰ Time complexity: O(m*n) as we will (m+1)*(n+1) table
  • 🧺 Space complexity: O(m * n)