Regular expression matching

Hard TimeO(n·m) SpaceO(n·m)

Match a string s against a pattern p where . matches any single character and * matches zero or more of the character immediately before it. The match must cover the whole string, not merely a part of it. A * always follows a character, and may match zero occurrences of it.

Examples

Example 1

Input
s = "aab"p = "c*a*b"
Output
true
c* takes no c at all, a* takes both as, and b matches b.

Example 2

Input
s = "aa"p = "a"
Output
false
The pattern accounts for one a and leaves the second over; a partial match does not count.

The Code

function isMatch(s, p) {
  const dp = [];
  for (let i = 0; i <= s.length; i++) {
    dp.push(new Array(p.length + 1).fill(false));
  }
  dp[0][0] = true;
  for (let j = 1; 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++) {
      if (p[j - 1] === "*") {
        dp[i][j] = dp[i][j - 2];
        if (p[j - 2] === "." || p[j - 2] === s[i - 1]) {
          if (dp[i - 1][j]) dp[i][j] = true;
        }
      } else if (p[j - 1] === "." || p[j - 1] === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }
  return dp[s.length][p.length];
}
isMatch("aab", "c*a*b");
Done

The first 12 calls, of 34. This one does not fit on a page.

Step through isMatch("aab", "c*a*b") call by call

More like this

All dynamic programming examples (20) →