LeetCode 44: Wildcard Matching Solution in Python Explained

Problem Statement

LeetCode 44, Wildcard Matching, is a hard-level problem where you’re given a string s and a pattern p. Your task is to determine if s matches p, where p can include wildcards: ? (matches any single character) and * (matches any sequence of characters, including empty). Return true if s fully matches p, false otherwise.

Constraints

  • 0 <= s.length, p.length <= 2000: String and pattern lengths are between 0 and 2000.
  • s contains only lowercase English letters.
  • p contains lowercase English letters, ?, and *.

Example

Input: s = "aa", p = "a"
Output: false
Explanation: "a" doesn’t match "aa" (too short).

Input: s = "aa", p = "*"
Output: true
Explanation: "*" matches any sequence, including "aa".

Input: s = "cb", p = "?a"
Output: false
Explanation: "?" matches "c", but "a" doesn’t match "b".

Input: s = "adceb", p = "*a*b"
Output: true
Explanation: "*a*b" matches "adceb" ("" + "a" + "dce" + "b").

Understanding the Problem

How do you solve LeetCode 44: Wildcard Matching in Python? For s = "adceb" and p = "*a*b", check if the pattern with wildcards matches the string—here, it does. The * can match any sequence, making this trickier than simple string matching. We’ll explore two approaches: a Dynamic Programming Solution (optimal and primary) and an Alternative with Two Pointers (greedy but complex). The DP method uses a table to track all possible matches efficiently.

Solution 1: Dynamic Programming Approach (Primary)

Explanation

Use a 2D DP table where dp[i][j] is true if the first i characters of s match the first j characters of p. Handle ? as a single-character match, * as zero or more characters, and build the table bottom-up.

Here’s a flow for s = "adceb", p = "*a*b":

dp[0][0] = true (empty matches empty)
dp[0][1] = true (* matches empty)
dp[1][2] = true ("a" matches "*a")
dp[5][4] = true ("adceb" matches "*a*b")
  1. Initialize DP Table.
  • Size = (len(s) + 1) x (len(p) + 1).
  1. Base Case.
  • Empty pattern matches empty string; * can match empty.
  1. Fill Table.
  • Handle exact matches, ?, and *.
  1. Return Result.
  • dp[len(s)][len(p)].

Step-by-Step Example

Example 1: s = "adceb", p = "ab"

We need true.

  • Goal: Check if pattern matches string.
  • Result for Reference: true.
  • Start: s = "adceb", p = "*a*b", dp = 6x5 table.
  • Step 1: Initialize.
    • dp[0][0] = true (empty matches empty).
    • dp[0][1] = true (* matches empty), dp[0][2] = false.
  • Step 2: i = 1, j = 1 (a vs *).
    • dp[1][1] = dp[1][0] (skip *) or dp[0][1] (use *) = false or true = true.
  • Step 3: i = 1, j = 2 (a vs a).
    • dp[1][2] = dp[0][1] (match a) = true.
  • Step 4: i = 5, j = 3 (adceb vs *a*).
    • dp[5][3] = dp[5][2] or dp[4][3] = true (skip or use *).
  • Step 5: i = 5, j = 4 (adceb vs b).
    • dp[5][4] = dp[4][3] and b == b = true.
  • Finish: dp[5][4] = true.

Example 2: s = "cb", p = "?a"

We need false.

  • Start: dp = 3x3.
  • Step 1: dp[0][0] = true.
  • Step 2: i = 1, j = 1 (c vs ?).
    • dp[1][1] = true (? matches c).
  • Step 3: i = 2, j = 2 (b vs a).
    • dp[2][2] = dp[1][1] and b != a = false.
  • Finish: dp[2][2] = false.

How the Code Works (Dynamic Programming)

Here’s the Python code with line-by-line explanation:

def isMatch(s: str, p: str) -> bool:
    # Line 1: Get lengths
    m, n = len(s), len(p)

    # Line 2: Initialize DP table
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True  # Empty matches empty

    # Line 3: Handle * at start of pattern
    for j in range(1, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-1]

    # Line 4: Fill DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                # Line 5: * matches zero or more
                dp[i][j] = dp[i][j-1] or dp[i-1][j]
            elif p[j-1] == '?' or s[i-1] == p[j-1]:
                # Line 6: ? or exact match
                dp[i][j] = dp[i-1][j-1]

    # Line 7: Return result
    return dp[m][n]

Alternative: Two Pointers Approach

Explanation

Use two pointers for s and p, with a star pointer to track the last *. When encountering *, move past it and try matching later characters, backtracking if needed.

  1. Initialize Pointers.
  2. Process Characters.
  • Match, move both; *, mark and skip; mismatch, backtrack.

3. Handle End Cases. 4. Return Result.

Step-by-Step Example (Alternative)

For s = "adceb", p = "*a*b":

  • Start: s_idx = 0, p_idx = 0, star = -1.
  • Step 1: p[0] = *, star = 0, p_idx = 1.
  • Step 2: s[0] = a, p[1] = a, match, s_idx = 1, p_idx = 2.
  • Step 3: p[2] = *, star = 2, p_idx = 3.
  • Step 4: s[4] = b, p[3] = b, match, s_idx = 5, p_idx = 4.
  • Finish: s_idx = 5, p_idx = 4, both at end, return true.

How the Code Works (Two Pointers)

def isMatchTwoPointers(s: str, p: str) -> bool:
    # Line 1: Initialize pointers
    s_idx, p_idx = 0, 0
    star = -1
    last_match = 0

    # Line 2: Process while within s
    while s_idx < len(s):
        # Line 3: Match or ?
        if (p_idx < len(p) and 
            (p[p_idx] == '?' or s[s_idx] == p[p_idx])):
            s_idx += 1
            p_idx += 1
        # Line 4: * encountered
        elif p_idx < len(p) and p[p_idx] == '*':
            star = p_idx
            last_match = s_idx
            p_idx += 1
        # Line 5: Mismatch, backtrack to last *
        elif star != -1:
            p_idx = star + 1
            last_match += 1
            s_idx = last_match
        else:
            return False

    # Line 6: Check remaining pattern
    while p_idx < len(p) and p[p_idx] == '*':
        p_idx += 1

    # Line 7: Return result
    return p_idx == len(p)

Complexity

  • Dynamic Programming:
    • Time: O(m * n) – Fill m x n table.
    • Space: O(m * n) – DP table.
  • Two Pointers:
    • Time: O(m * n) – Worst case with backtracking.
    • Space: O(1) – Only pointers.

Efficiency Notes

DP is O(m * n) time and space, reliable and clear for LeetCode 44. Two Pointers is O(1) space but can be O(m * n) time with backtracking, less predictable but space-efficient.

Key Insights

Tips to master LeetCode 44:

  • *** Flexibility**: Matches zero or more, key to DP logic.
  • Table Thinking: Build matches incrementally.
  • Edge Cases: Handle empty and all-* patterns.

Additional Example

For s = "abcde", p = "a?c*":

  • Goal: true.
  • DP: dp[5][4] = true (a?c matches abc, * matches de).
  • Result: true.

Edge Cases

  • Empty String: s = "", p = "*" – Return true.
  • No Match: s = "aa", p = "a" – Return false.
  • All Stars: s = "abc", p = "***" – Return true.

Final Thoughts

The Dynamic Programming solution is a rock-solid choice for LeetCode 44 in Python—systematic and effective for wildcard matching. For a related challenge, try LeetCode 43: Multiply Strings to switch gears with string math! Ready to match some patterns? Solve LeetCode 44 on LeetCode now and test it with "abcde" or "??" to master wildcards. Dive in and nail it!