NUHMAN.com

Introduction

LeetCode 44: Wildcard Matching is a problem where you're asked to determine if a given string matches a pattern that includes wildcard characters. The wildcard characters are:

• * which matches any sequence of characters (including an empty sequence).
• ? which matches exactly one character.

This problem requires implementing a dynamic programming solution, as it's similar to regular expression matching, but with simpler wildcard rules.

Problem Statement

Given a string s and a pattern p, return true if s matches the pattern, otherwise return false. The pattern may contain the following wildcard characters:

• ? matches any single character.
• * matches any sequence of characters (including an empty sequence).

Examples

go

Input: s = "aa", p = "a*"
Output: true
go

Input: s = "mississippi", p = "mis*is*p*."
Output: false
go

Input: s = "ab", p = "?*"
Output: true

Approach: Dynamic Programming

We can solve this problem using a 2D dynamic programming (DP) table where each entry dp[i][j] represents whether the first i characters of string s match the first j characters of pattern p.

Steps:

1. Initialize a DP Table:

• Let dp[i][j] be true if the first i characters of s match the first j characters of p. Otherwise, dp[i][j] is false.
• Set dp[0][0] = true because an empty string matches an empty pattern.

1. Handle * in the Pattern:

• If the current character in the pattern is *, it can either match an empty sequence or match one or more characters from the string s.
• This can be represented as:
• dp[i][j] = dp[i][j-1] || dp[i-1][j], where dp[i][j-1] indicates the * matches an empty sequence and dp[i-1][j] indicates the * matches one or more characters.

1. Handle ? in the Pattern:

• If the current character in the pattern is ?, it matches exactly one character from s. So, dp[i][j] = dp[i-1][j-1].

1. Handle Exact Character Matches:

• If the current characters in both the string and the pattern are the same (or the pattern character is ?), then dp[i][j] = dp[i-1][j-1].

1. Final Result:

• After filling the DP table, dp[m][n] will contain the result, where m is the length of string s and n is the length of pattern p.

Go Implementation

go

func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    
    // DP table where dp[i][j] represents whether s[0..i-1] matches p[0..j-1]
    dp := make([][]bool, m+1)
    for i := range dp {
        dp[i] = make([]bool, n+1)
    }
    
    // Initialize the DP table
    dp[0][0] = true
    
    // Handle the case where the pattern starts with '*' (matches empty string)
    for j := 1; j <= n; j++ {
        if p[j-1] == '*' {
            dp[0][j] = dp[0][j-1]
        }
    }
    
    // Fill the DP table
    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]
            } else if p[j-1] == '?' || s[i-1] == p[j-1] {
                dp[i][j] = dp[i-1][j-1]
            }
        }
    }

    return dp[m][n]
}

Example Walkthrough

Example 1:

go

Input: s = "aa", p = "a*"

1. Initialization:

• dp[0][0] = true
• For j = 1, dp[0][1] = false
• For j = 2, dp[0][2] = true (as * can match empty sequence).

1. Filling the DP Table:

• For i = 1, dp[1][1] = true (as a matches a).
• For i = 1, dp[1][2] = true (as * can match the empty sequence).

1. Output: dp[2][2] = true (i.e., "aa" matches "a*").

Example 2:

go

Input: s = "mississippi", p = "mis*is*p*."

1. Initialization:

• Start with dp[0][0] = true.
• Handle * in the pattern, filling the DP table based on the wildcard matching logic.

1. Filling the DP Table:

• The matching fails when trying to match characters p[8] and p[9] against the string.

1. Output: dp[11][11] = false (i.e., "mississippi" does not match "misisp*.").

Time and Space Complexity

MetricComplexityTime ComplexityO(m * n)Space ComplexityO(m * n)

• Time Complexity: The algorithm iterates over a 2D DP table of size m * n, where m is the length of string s and n is the length of pattern p. Hence, the time complexity is O(m * n).
• Space Complexity: We use a 2D DP table of size (m+1) x (n+1), so the space complexity is O(m * n).

Edge Cases

• Empty String or Pattern: If either the string s or the pattern p is empty, handle accordingly.
• An empty string matches an empty pattern or a pattern consisting solely of *.
• An empty pattern matches an empty string.
• Pattern with Only Wildcards: A pattern consisting of only * can match any string, including an empty string.
• Pattern with Only Exact Matches: If the pattern consists of characters without wildcards, it must match the string exactly.

Key Takeaways

• Dynamic programming is an optimal solution for problems involving pattern matching with wildcards.
• The 2D DP table helps break the problem into subproblems, solving the problem for each prefix of s and p.
• Edge cases like empty strings, patterns with only *, or exact matches should be carefully handled.