04 Aug 2023•Hard•PHP

Wildcard Matching

match string against pattern with ? and * using dynamic programming.

dp[i][j] = true if s[0..i] matches p[0..j]. ? matches any single character. * matches any sequence including empty.

for *, try matching zero characters (skip *) or one or more characters (consume string). can optimize space to O(n) by using only previous row.

cases

exact match: s[i] == p[j]
?: p[j] == '?' matches any character
*: matches zero or more characters

complexity

O(mn) time where m and n are string and pattern lengths. O(mn) space, can be optimized to O(n).

Solution files

PHP•wildcard-matching/solution.php

class Solution {

function isMatch($s, $p) {
    $m = strlen($s);
    $n = strlen($p);

    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, false));

    $dp[0][0] = true;

    for ($j = 1; $j <= $n; $j++) {
        if ($p[$j - 1] == '*') {
            $dp[0][$j] = $dp[0][$j - 1];
        }
    }

    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++){
            if ($p[$j - 1] == '*') {
                $dp[$i][$j] = $dp[$i][$j - 1] || $dp[$i - 1][$j];
            } elseif ($p[$j - 1] == '?' || $s[$i - 1] == $p[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1];
            }
        }
    }

    return $dp[$m][$n];
}
}

$solution = new Solution();
var_dump($solution->isMatch("aa", "a"));
var_dump($solution->isMatch("aa", "*"));
var_dump($solution->isMatch("cb", "?a"));