Wildcard matching

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

Match a string s against a pattern p where ? matches exactly one character, never zero, and * matches any run of characters, an empty one included. Unlike the regular-expression form, a * here stands alone rather than repeating the character before it. The match must cover the whole string.

Examples

Example 1

Input
s = "adceb"p = "*a*b"
Output
true
The first * takes nothing, a matches a, the second * takes dce, and b matches b.

Example 2

Input
s = "acdcb"p = "a*c?b"
Output
false
a matches, but nothing the * can take leaves c?b exactly three characters to finish on.

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 - 1];
  }
  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 - 1][j] || dp[i][j - 1];
      } 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("adceb", "*a*b");
Done

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

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

More like this

All dynamic programming examples (20) →