Wildcard matching
Hard'*' either consumes a character or nothing
Problem
Match a string against a pattern with '?' (any one char) and '*' (any sequence).
Fill a match grid where '*' can skip characters and '?' matches any single one.
The idea
A '?' matches exactly one character, and a '*' branches: either it absorbs the current character and stays available, or it matches empty and the pattern advances. Those two branches are the entire recurrence.
The trick
- '*': dp[i-1][j] (consume a character) OR dp[i][j-1] (match empty).
- A pattern of only stars matches the empty string.
- O(m·n).
Step 1 of 8. LCS grid for "ABC" and "AC". Match → diagonal + 1, else the best of up/left.
Match extends the diagonal.
1for (let i = 1; i <= n; i++)2 for (let j = 1; j <= m; j++)3 dp[i][j] = a[i-1] === b[j-1]4 ? dp[i-1][j-1] + 15 : Math.max(dp[i-1][j], dp[i][j-1]);Input
- grid
- 5 × 4
Memory
- at
- —
- cells marked
- 0
Output
- LCS
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s = "adceb", p = "*a*b"
- Output:
- true
- Explanation:
- The stars stretch to cover the middle.
Example 2
- Input:
- s = "cb", p = "?a"
- Output:
- false
- Explanation:
- 'a' doesn't match 'b' → false.
Example 3
- Input:
- s = "abc", p = "*"
- Output:
- true
- Explanation:
- A single * matches anything.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.