#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/lcs-and-edit-distance/wildcard-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/lcs-and-edit-distance/wildcard-implementation

Repovive

LeetCode 44 Wildcard Matching - Implementation - LCS and Edit Distance | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 44 Wildcard Matching - Implementation

The code

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].