Home/Learn/Wildcard & Regex Matching

Pattern Guide

Wildcard & Regex Matching

"DP for pattern matching. Wildcard '?' and '*', regex '.' and '*'."

Pattern matching with special characters uses 2D DP: dp[i][j] = does pattern[0..i-1] match string[0..j-1]. Wildcard: '?' matches any single char; '*' matches any sequence (including empty). Regex: '.' matches any single char; '*' makes the preceding element occur 0+ times. Key difference: wildcard '*' is greedy (matches any sequence directly), regex '*' depends on the preceding character.

14 min readdp problems →

Problems you can solve with this pattern

4 problems · click any to start solving

All dp →
1Regular Expression MatchingHardSolve
2Wildcard MatchingHardSolve
3Longest Valid ParenthesesHardSolve
4Word PatternEasySolve
Wildcard and regex matching DP
// Wildcard matching: ? matches any char, * matches any sequence
function wildcardMatch(s, p) {
    const m = p.length, n = s.length;
    const dp = Array.from({length: m+1}, () => new Array(n+1).fill(false));
    dp[0][0] = true;
    // p[0..i-1] of all '*' can match empty string
    for (let i = 1; i <= m; i++) dp[i][0] = dp[i-1][0] && p[i-1] === '*';

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[i-1] === '*')
                dp[i][j] = dp[i-1][j] || dp[i][j-1]; // skip* or consume char
            else if (p[i-1] === '?' || p[i-1] === s[j-1])
                dp[i][j] = dp[i-1][j-1];
        }
    }
    return dp[m][n];
}

Wildcard dp[i][j]: p[i]='?' → dp[i-1][j-1] (match any char). p[i]='*' → dp[i-1][j] (use * for empty) OR dp[i][j-1] (use * to match one more char). Else: dp[i-1][j-1] && p[i]==s[j]. Regex dp[i][j]: p[i]='.' → dp[i-1][j-1]. p[i]='*' → dp[i-2][j] (0 occurrences) OR (dp[i][j-1] && (p[i-1]=='.' || p[i-1]==s[j])) (1+ occurrences). Else: dp[i-1][j-1] && p[i]==s[j].

Wildcard and regex matching DP
// Wildcard matching: ? matches any char, * matches any sequence
function wildcardMatch(s, p) {
    const m = p.length, n = s.length;
    const dp = Array.from({length: m+1}, () => new Array(n+1).fill(false));
    dp[0][0] = true;
    // p[0..i-1] of all '*' can match empty string
    for (let i = 1; i <= m; i++) dp[i][0] = dp[i-1][0] && p[i-1] === '*';

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[i-1] === '*')
                dp[i][j] = dp[i-1][j] || dp[i][j-1]; // skip* or consume char
            else if (p[i-1] === '?' || p[i-1] === s[j-1])
                dp[i][j] = dp[i-1][j-1];
        }
    }
    return dp[m][n];
}
1
Regular Expression Matching
Hard
Solve
2
Wildcard Matching
Hard
Solve
3
Longest Valid Parentheses
Hard
Solve
4
Word Pattern
Easy
Solve
Wildcard vs Regex '*' difference:
- Wildcard '*': matches any sequence of characters directly
- Regex '*': makes the PRECEDING element repeat 0+ times

Regex base cases:
- dp[0][0] = true (empty pattern matches empty string)
- dp[i][0] = dp[i-2][0] if p[i-1]=='*' (x* can match empty)

Greedy alternative for wildcard: Two pointers with backtracking — when '*' is encountered, record position; if mismatch, retreat to last '*' and try consuming one more char. O(n) average but O(mn) worst case.
← String Decode & Transform PatternsBST Operations & Properties →