Wildcard Matching - Practice Coding Problems

Wildcard Matching - Problem

Given an input string s and a pattern p, implement wildcard pattern matching with support for '?' and '*':

'?' Matches any single character
'*' Matches any sequence of characters (including the empty sequence)

The matching should cover the entire input string (not partial). Return true if the pattern matches the string, false otherwise.

Input & Output

Example 1 — Basic Wildcard Match

$ Input: s = "abc", p = "a*c"

› Output: true

💡 Note: Pattern 'a*c' matches 'abc': 'a' matches 'a', '*' matches 'b', 'c' matches 'c'

Example 2 — No Match

$ Input: s = "abc", p = "a*d"

› Output: false

💡 Note: Pattern 'a*d' cannot match 'abc': 'a' matches 'a', '*' can match 'b', but 'd' cannot match 'c'

Example 3 — Question Mark Wildcard

$ Input: s = "abc", p = "a?c"

› Output: true

💡 Note: Pattern 'a?c' matches 'abc': 'a' matches 'a', '?' matches 'b', 'c' matches 'c'

Constraints

0 ≤ s.length, p.length ≤ 2000
s contains only lowercase English letters
p contains only lowercase English letters, '?' or '*'

Visualization

Tap to expand

Understanding the Visualization

Input

String 'abc' and pattern 'a*c' with wildcards

Process

Match character by character, handling wildcards

Output

True if entire string matches pattern

Key Takeaway

🎯 Key Insight: Use DP to break the problem into subproblems: does pattern[0:j] match string[0:i]?

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is recognizing this as a dynamic programming problem where we need to determine if pattern[0:j] matches string[0:i]. The optimal approach uses either 2D DP for clarity or greedy two pointers for space efficiency. Time: O(m×n), Space: O(m×n) for DP or O(1) for greedy.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Two Pointers	O(m×n)	O(1)	Use two pointers with greedy matching strategy for '*' wildcards
Recursion with Memoization	O(m×n)	O(m×n)	Add memoization to the recursive solution to cache results
Recursive Brute Force	O(2^(m+n))	O(m+n)	Recursively try all possible ways the pattern can match the string
Dynamic Programming (2D Table)	O(m×n)	O(m×n)	Build a 2D DP table bottom-up to solve all subproblems

Greedy Two Pointers — Algorithm Steps

Use two pointers for string and pattern
Match characters directly when possible
For '*', save position and try matching greedily
Backtrack if current path fails

Visualization

Tap to expand

Step-by-Step Walkthrough

Forward

Move pointers forward when characters match

Star Save

Save position when encountering '*'

Backtrack

Backtrack to last '*' if matching fails

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* s, char* p) {
    int sIdx = 0, pIdx = 0;
    int starIdx = -1, sMatch = -1;
    int sLen = strlen(s), pLen = strlen(p);
    
    while (sIdx < sLen) {
        // If characters match, advance both pointers
        if (pIdx < pLen && (p[pIdx] == '?' || p[pIdx] == s[sIdx])) {
            sIdx++;
            pIdx++;
        }
        // If pattern char is '*', record position and advance pattern
        else if (pIdx < pLen && p[pIdx] == '*') {
            starIdx = pIdx;
            sMatch = sIdx;
            pIdx++;
        }
        // If no match and we have seen '*', backtrack
        else if (starIdx != -1) {
            pIdx = starIdx + 1;
            sMatch++;
            sIdx = sMatch;
        }
        else {
            return false;
        }
    }
    
    // Skip any remaining '*' in pattern
    while (pIdx < pLen && p[pIdx] == '*') {
        pIdx++;
    }
    
    return pIdx == pLen;
}

int main() {
    char s[1000], p[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    fgets(p, sizeof(p), stdin);
    p[strcspn(p, "\n")] = 0;
    
    bool result = solution(s, p);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

In worst case, backtracking explores m×n combinations

✓ Linear Growth

Space Complexity

O(1)

Only uses a few pointer variables, no extra arrays

✓ Linear Space

78.0K Views

Medium Frequency

~25 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Two Pointers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler