04 Aug 2023•PHP•Hard

Wildcard Matching

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

View original LeetCode question

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(class="syntax-number">0, $m + class="syntax-number">1, array_fill(class="syntax-number">0, $n + class="syntax-number">1, false));

    $dp[class="syntax-number">0][class="syntax-number">0] = true;

    for ($j = class="syntax-number">1; $j <= $n; $j++) {
        if ($p[$j - class="syntax-number">1] == class="syntax-string">'*') {
            $dp[class="syntax-number">0][$j] = $dp[class="syntax-number">0][$j - class="syntax-number">1];
        }
    }

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

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

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