DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 70: Python Wildcard Matching – DP Solution for '?' and '*' Patterns in O(n*m) (LeetCode #44 Mastery)

#challenge #python #algorithms #programming

Welcome to Day 70 of the #80DaysOfChallenges journey! This intermediate challenge implements wildcard pattern matching with '?' (single char) and '*' (zero or more chars) using dynamic programming in a 2D table, solving the tough LeetCode #44 problem in O(n*m) time. It handles complex patterns like "a*b?c" against strings, with DP states tracking matches for empty/partial text/pattern. If you're grinding hard DP string problems, prepping for interviews, or building search/filters with wildcards, this "Python wildcard matching" script is efficient, handles all cases, and the exact bottom-up DP recruiters expect.

💡 Key Takeaways from Day 70: Wildcard Matching Function

This task features a DP table where dp[i][j] means text[:i] matches pattern[:j], with special rules for '?' and ''. It's a state transition pattern: exact/? diagonal, * zero/one choice. We'll detail: **function with DP init and * prefix, **nested loops for state fill, and **main with input test*.

1. Function Design: DP Table and Base Cases

The wildcard_match function builds (n+1) x (m+1) table:

def wildcard_match(text: str, pattern: str) -> bool:
    """Return True if text matches the wildcard pattern."""
    n = len(text)
    m = len(pattern)

    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True                 # empty text matches empty pattern

    # handle patterns starting with '*'
    for j in range(1, m + 1):
        if pattern[j - 1] == "*":
            dp[0][j] = dp[0][j - 1]
Enter fullscreen mode Exit fullscreen mode

dp[0][0] true for empty. For empty text, only * patterns match (zero chars). This seeds * prefixes.

2. Fill Loops: Rules for ?, Literal, and *

Core nested fill:

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if pattern[j - 1] == text[i - 1] or pattern[j - 1] == "?":
                dp[i][j] = dp[i - 1][j - 1]      # exact or single-char match
            elif pattern[j - 1] == "*":
                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
                # '*' matches empty or one/more characters
Enter fullscreen mode Exit fullscreen mode

If literal or ?, take diagonal (match prev). If *, take left (empty) or above (one more). Covers zero/many.

3. Return and Main: Bottom-Right and Input

Returns dp[n][m] for full match.

Main tests:

text = input("Enter text: ").strip()
pattern = input("Enter pattern (? and * supported): ").strip()

result = wildcard_match(text, pattern)
print(f"Match result: {result}")
Enter fullscreen mode Exit fullscreen mode

Interactive, try "aa" with "a*" → True, "aa" with "c*a" → False.

🎯 Summary and Reflections

This wildcard DP handles * zero/many with or choice. It reinforced:

  • DP for strings: Table for partial matches.
  • *** flexibility**: Left/above or for empty/one+.
  • Prefix * init: Key for leading stars.

Reflections: Space optimize to 1D row. Regex alternative but DP teaches state.

Advanced Alternatives: Greedy two-pointer. Recursion with memo. Your pattern match? Share!

🚀 Next Steps and Resources

Day 70 conquered wildcard DP. In #80DaysOfChallenges? Regex version? Post!

Top comments (0)