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]
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
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}")
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!
Source Code for Challenge #70: scripts/wildcard_matching.py
Main Repository: 80-days-of-challenges
Daily Updates: Twitter/X (@Shahrouzlogs)