LeetCode 44 Wildcard Matching - Implementation

function isMatch(s, p)
    m := length of s
    n := length of p
    dp := 2D array (m + 1) x (n + 1), all false
    dp[0][0] := true
    // Empty string matches empty pattern
    // Handle leading *'s in pattern
    for j from 1 to n
        if p[j - 1] = '*'
            dp[0][j] := dp[0][j - 1]
    for i from 1 to m
        for j from 1 to n
            if p[j - 1] = '*'
                dp[i][j] := dp[i][j - 1] OR dp[i - 1][j]
            else if p[j - 1] = '?' OR p[j - 1] = s[i - 1]
                dp[i][j] := dp[i - 1][j - 1]
    return dp[m][n]

Time: $O(mn)$. Space: $O(mn)$, reducible to $O(n)$.

For *: either use it to match zero characters (dp[i][j-1]) or match one more character (dp[i-1][j]). For ? or exact match: extend from dp[i-1][j-1].