Regular Expression Matching

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

 

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 <= 30
• 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

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    const dp = Array(s.length + 1)
        .fill(null)
        .map(() => Array(p.length + 1).fill(false));

    dp[0][0] = true; // empty string matches empty pattern

    // empty string matches pattern when all letters in pattern has * quantifier
    for (let j = 2; j <= p.length; j++) {
        if (p[j - 1] === "*") {
            dp[0][j] = dp[0][j - 2];
        }
    }

    for (let i = 1; i <= s.length; i++) {
        for (let j = 1; j <= p.length; j++) {
            const c = s[i - 1]; // current character in s
            if (c === p[j - 1] || p[j - 1] === ".") { // c matches pattern character
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === "*") { // * quantifier
                dp[i][j] = dp[i][j - 2]; // * possibly match 0 characters
                if (c === p[j - 2] || p[j - 2] === ".") { // c matches pattern character before * (ie. * can match c)
                    dp[i][j] ||= dp[i - 1][j];
                }
            }
        }
    }
    return dp[s.length][p.length];
};

We will implement a DP solution. Let dp[i][j] be whether the pattern p[0:j] matches the string s[0:i].

• For the base case:
  • If i = 0, then dp[0][j] = true if and only if every letter in p[0:j] is followed by the '*' quantifier (eg. p = c*c*c*c*c*c* for any letters c). This is because the '*' quantifier allows zero matches, which makes it possible to match the empty string s[0:0].
  • If j = 0, then dp[i][0] = false for i != 0, since the empty pattern can only match the empty string.
• For the recursive case:
  • If the current character si of s equals the current character pj of p (also counts if pj is '.'), then pj matches si, and the current p matches the current s only if the previous p matches the previous s (ie. not including pj and si).
  • Otherwise, if pj == '*', then the '*' quantifier can possibly match zero characters in s (ie. we can ignore it), and so if p without the quantifier matches the current s, by including the quantifier p must still match the current s. In addition, if si equals the character associated with the quantifier (also counts if the character is '.'), then the quantifier can match si, and so it only depends on whether the current p matches the previous s (ie. not including si).

Note that the way we fill in the base case for i = 0 is to use 1D DP. More specifically, if the current character in p is the '*' quantifier, and the pattern not including the quantifier or the letter associated with said quantifier matches the empty string, then including the letter and quantifier must also match the empty string (ie. if pattern p matches the empty string, then p + c* must also match the empty string).