Wildcard Matching

🎯

Wildcard Matching

hardDPFacebookAmazonGoogle

Imagine building a search feature that supports '?' and '*' wildcards, allowing users to find files or data with flexible patterns.

💡 This problem is a classic example of string dynamic programming where naive greedy approaches fail due to the complexity introduced by the '*' wildcard. Beginners often struggle to understand why simple matching doesn't work and how to systematically explore all possibilities efficiently.

📋

Problem Statement

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). Return true if the pattern matches the entire input string, otherwise false.

1 ≤ s.length, p.length ≤ 10^5s contains only lowercase English lettersp contains only lowercase English letters, '?' or '*'

💡

Example

Input"s = 'aa', p = 'a'"

Outputfalse

'a' does not match the entire string 'aa'

Input"s = 'aa', p = '*'"

Outputtrue

'*' matches any sequence including 'aa'

Input"s = 'cb', p = '?a'"

Outputfalse

'?' matches 'c', but 'a' does not match 'b'

Input"s = 'adceb', p = '*a*b'"

Outputtrue

'*' matches 'adc', 'a' matches 'a', '*' matches 'e', 'b' matches 'b'

• Empty string s and pattern p = '*' → true
• Pattern p with multiple consecutive '*' → treated as one '*'
• String s with repeated characters and pattern with '?' only → matches if lengths equal
• Pattern p longer than string s with no '*' → false

🔁

Why DP?

Why greedy fails:

Greedy fails because '*' can match any sequence, so choosing to match zero or more characters greedily can miss valid matches. For example, s='ab', p='*b' greedy matching '*' as empty fails, but matching '*' as 'a' succeeds.

DP state:

dp[i][j] = true if the first i characters of s match the first j characters of p, false otherwise.

Recurrence:dp[i][j] = (p[j-1] == s[i-1] or p[j-1] == '?') and dp[i-1][j-1] or p[j-1] == '*' and (dp[i][j-1] or dp[i-1][j])

If current pattern char matches current string char or is '?', result depends on previous prefixes. If '*', it can match empty (dp[i][j-1]) or one more char (dp[i-1][j]).

⚠️

Common Mistakes

Not handling empty string and pattern correctly

Incorrect match results for empty inputs

✅ Initialize dp[0][0] = True and handle empty prefix cases

Treating multiple consecutive '*' as separate wildcards

Redundant computations and incorrect matches

✅ Preprocess pattern to merge consecutive '*' into one

Incorrectly updating dp array in space optimized approach

Overwrites needed values leading to wrong results

✅ Iterate backwards on pattern indices when updating 1D dp

Confusing '?' wildcard with '*' wildcard

Matching logic fails, producing wrong outputs

✅ Remember '?' matches exactly one char, '*' matches zero or more

🧠

Brute Force (Pure Recursion)

💡 This approach explores all possible ways '*' can match sequences, helping understand the problem's exponential complexity and why optimization is needed.

Intuition

Try to match characters one by one. If pattern char is '*', try matching zero or more characters recursively.

Algorithm

1. If both strings are fully matched, return true.
2. If pattern is exhausted but string is not, return false.
3. If current pattern char is '*', recursively try matching zero or more chars.
4. If current pattern char is '?' or matches current string char, recurse on next chars.

💡 The recursion tree grows exponentially because '*' branches into multiple recursive calls, making it hard to follow without memoization.

Recurrence:match(i, j) = (p[j] == '*') ? match(i, j+1) or match(i+1, j) : (p[j] == s[i] or p[j] == '?') and match(i+1, j+1)

</>

Code

def isMatch(s: str, p: str) -> bool:
    def dfs(i, j):
        if i == len(s) and j == len(p):
            return True
        if j == len(p):
            return False
        if p[j] == '*':
            if dfs(i, j+1):
                return True
            if i < len(s) and dfs(i+1, j):
                return True
            return False
        if i < len(s) and (p[j] == s[i] or p[j] == '?'):
            return dfs(i+1, j+1)
        return False
    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    print(isMatch('adceb', '*a*b'))  # True
    print(isMatch('aa', 'a'))       # False

Line Notes

def dfs(i, j):Defines recursive helper to match s[i:] and p[j:]

if i == len(s) and j == len(p):Base case: both strings fully matched

if p[j] == '*':Handle '*' wildcard by trying zero or more matches

if i < len(s) and (p[j] == s[i] or p[j] == '?')Match single char or '?' wildcard

public class Solution {
    public boolean isMatch(String s, String p) {
        return dfs(s, p, 0, 0);
    }
    private boolean dfs(String s, String p, int i, int j) {
        if (i == s.length() && j == p.length()) return true;
        if (j == p.length()) return false;
        if (p.charAt(j) == '*') {
            if (dfs(s, p, i, j + 1)) return true;
            if (i < s.length() && dfs(s, p, i + 1, j)) return true;
            return false;
        }
        if (i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')) {
            return dfs(s, p, i + 1, j + 1);
        }
        return false;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isMatch("adceb", "*a*b")); // true
        System.out.println(sol.isMatch("aa", "a"));       // false
    }
}

Line Notes

public boolean isMatch(String s, String p)Entry point for matching s and p

if (i == s.length() && j == p.length())Both strings fully matched

if (p.charAt(j) == '*')Try zero or more matches for '*'

if (i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?'))Match single char or '?'

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    bool dfs(const string& s, const string& p, int i, int j) {
        if (i == s.size() && j == p.size()) return true;
        if (j == p.size()) return false;
        if (p[j] == '*') {
            if (dfs(s, p, i, j + 1)) return true;
            if (i < s.size() && dfs(s, p, i + 1, j)) return true;
            return false;
        }
        if (i < s.size() && (p[j] == s[i] || p[j] == '?')) {
            return dfs(s, p, i + 1, j + 1);
        }
        return false;
    }
    bool isMatch(string s, string p) {
        return dfs(s, p, 0, 0);
    }
};

int main() {
    Solution sol;
    cout << boolalpha << sol.isMatch("adceb", "*a*b") << endl; // true
    cout << boolalpha << sol.isMatch("aa", "a") << endl;       // false
    return 0;
}

Line Notes

bool dfs(const string& s, const string& p, int i, int j)Recursive helper matching s[i:] and p[j:]

if (i == s.size() && j == p.size())Both strings fully matched

if (p[j] == '*')Handle '*' by trying zero or more matches

if (i < s.size() && (p[j] == s[i] || p[j] == '?'))Match single char or '?'

function isMatch(s, p) {
    function dfs(i, j) {
        if (i === s.length && j === p.length) return true;
        if (j === p.length) return false;
        if (p[j] === '*') {
            if (dfs(i, j + 1)) return true;
            if (i < s.length && dfs(i + 1, j)) return true;
            return false;
        }
        if (i < s.length && (p[j] === s[i] || p[j] === '?')) {
            return dfs(i + 1, j + 1);
        }
        return false;
    }
    return dfs(0, 0);
}

// Example usage
console.log(isMatch('adceb', '*a*b')); // true
console.log(isMatch('aa', 'a'));       // false

Line Notes

function dfs(i, j)Recursive function to match s[i:] and p[j:]

if (i === s.length && j === p.length)Both strings fully matched

if (p[j] === '*')Try zero or more matches for '*'

if (i < s.length && (p[j] === s[i] || p[j] === '?'))Match single char or '?'

⏱

Complexity

TimeO(2^(m+n))

SpaceO(m+n) due to recursion stack

Each '*' can branch into two recursive calls, leading to exponential growth in worst case.

💡 For strings of length 20, this can mean over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's complexity and motivate DP.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving efficiency over brute force.

Intuition

Use recursion but store results of dp[i][j] to avoid repeated work. This exploits overlapping subproblems.

Algorithm

1. Initialize a memo dictionary to store results for (i, j).
2. If (i, j) in memo, return stored result.
3. Apply same logic as brute force but store results before returning.
4. Return memo[(i, j)] as the result for current state.

💡 Memoization adds a caching layer that transforms exponential recursion into polynomial time.

Recurrence:dp[i][j] = (p[j] == '*') ? dp[i][j+1] or dp[i+1][j] : (p[j] == s[i] or p[j] == '?') and dp[i+1][j+1]

</>

Code

def isMatch(s: str, p: str) -> bool:
    memo = {}
    def dfs(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if i == len(s) and j == len(p):
            return True
        if j == len(p):
            return False
        if p[j] == '*':
            memo[(i, j)] = dfs(i, j+1) or (i < len(s) and dfs(i+1, j))
            return memo[(i, j)]
        if i < len(s) and (p[j] == s[i] or p[j] == '?'):
            memo[(i, j)] = dfs(i+1, j+1)
            return memo[(i, j)]
        memo[(i, j)] = False
        return False
    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    print(isMatch('adceb', '*a*b'))  # True
    print(isMatch('aa', 'a'))       # False

Line Notes

memo = {}Cache to store results of subproblems

if (i, j) in memo:Return cached result to avoid recomputation

memo[(i, j)] = dfs(i, j+1) or (i < len(s) and dfs(i+1, j))Store result for '*' wildcard matching zero or more chars

memo[(i, j)] = dfs(i+1, j+1)Store result for matching single char or '?'

import java.util.*;
public class Solution {
    Map<String, Boolean> memo = new HashMap<>();
    public boolean isMatch(String s, String p) {
        return dfs(s, p, 0, 0);
    }
    private boolean dfs(String s, String p, int i, int j) {
        String key = i + "," + j;
        if (memo.containsKey(key)) return memo.get(key);
        if (i == s.length() && j == p.length()) return true;
        if (j == p.length()) return false;
        boolean ans;
        if (p.charAt(j) == '*') {
            ans = dfs(s, p, i, j + 1) || (i < s.length() && dfs(s, p, i + 1, j));
        } else if (i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')) {
            ans = dfs(s, p, i + 1, j + 1);
        } else {
            ans = false;
        }
        memo.put(key, ans);
        return ans;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isMatch("adceb", "*a*b")); // true
        System.out.println(sol.isMatch("aa", "a"));       // false
    }
}

Line Notes

Map<String, Boolean> memo = new HashMap<>();Cache for storing subproblem results

if (memo.containsKey(key)) return memo.get(key);Return cached result if available

ans = dfs(s, p, i, j + 1) || (i < s.length() && dfs(s, p, i + 1, j));Handle '*' wildcard with memoization

memo.put(key, ans);Store computed result before returning

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
    unordered_map<string, bool> memo;
public:
    bool dfs(const string& s, const string& p, int i, int j) {
        string key = to_string(i) + "," + to_string(j);
        if (memo.count(key)) return memo[key];
        if (i == s.size() && j == p.size()) return true;
        if (j == p.size()) return false;
        bool ans;
        if (p[j] == '*') {
            ans = dfs(s, p, i, j + 1) || (i < s.size() && dfs(s, p, i + 1, j));
        } else if (i < s.size() && (p[j] == s[i] || p[j] == '?')) {
            ans = dfs(s, p, i + 1, j + 1);
        } else {
            ans = false;
        }
        memo[key] = ans;
        return ans;
    }
    bool isMatch(string s, string p) {
        return dfs(s, p, 0, 0);
    }
};

int main() {
    Solution sol;
    cout << boolalpha << sol.isMatch("adceb", "*a*b") << endl; // true
    cout << boolalpha << sol.isMatch("aa", "a") << endl;       // false
    return 0;
}

Line Notes

unordered_map<string, bool> memo;Cache to store results of subproblems

if (memo.count(key)) return memo[key];Return cached result if available

ans = dfs(s, p, i, j + 1) || (i < s.size() && dfs(s, p, i + 1, j));Handle '*' wildcard with memoization

memo[key] = ans;Store computed result before returning

function isMatch(s, p) {
    const memo = new Map();
    function dfs(i, j) {
        const key = i + ',' + j;
        if (memo.has(key)) return memo.get(key);
        if (i === s.length && j === p.length) return true;
        if (j === p.length) return false;
        let ans;
        if (p[j] === '*') {
            ans = dfs(i, j + 1) || (i < s.length && dfs(i + 1, j));
        } else if (i < s.length && (p[j] === s[i] || p[j] === '?')) {
            ans = dfs(i + 1, j + 1);
        } else {
            ans = false;
        }
        memo.set(key, ans);
        return ans;
    }
    return dfs(0, 0);
}

// Example usage
console.log(isMatch('adceb', '*a*b')); // true
console.log(isMatch('aa', 'a'));       // false

Line Notes

const memo = new Map();Cache to store subproblem results

if (memo.has(key)) return memo.get(key);Return cached result if available

ans = dfs(i, j + 1) || (i < s.length && dfs(i + 1, j));Handle '*' wildcard with memoization

memo.set(key, ans);Store computed result before returning

⏱

Complexity

TimeO(m*n)

SpaceO(m*n) due to memoization cache and recursion stack

Each state (i, j) is computed once and cached, reducing exponential calls to polynomial.

💡 For strings of length 1000, this means up to 1 million states, which is feasible.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for large inputs and is a common interview expectation.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively from smaller subproblems, often easier to debug and understand than recursion.

Intuition

Create a 2D dp table where dp[i][j] indicates if s[:i] matches p[:j]. Fill table row by row using recurrence.

Algorithm

1. Initialize dp array with False, set dp[0][0] = True for empty strings.
2. Pre-fill first row for patterns starting with '*' that can match empty string.
3. Iterate over s and p indices, fill dp[i][j] based on pattern char:
4. If '*', dp[i][j] = dp[i][j-1] or dp[i-1][j]; else if '?' or char match, dp[i][j] = dp[i-1][j-1].

💡 Filling the dp table systematically ensures all subproblems are solved before dependent ones.

Recurrence:dp[i][j] = (p[j-1] == '*') ? dp[i][j-1] or dp[i-1][j] : (p[j-1] == s[i-1] or p[j-1] == '?') and dp[i-1][j-1]

</>

Code

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
            elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]

# Example usage
if __name__ == '__main__':
    print(isMatch('adceb', '*a*b'))  # True
    print(isMatch('aa', 'a'))       # False

Line Notes

dp = [[False] * (n + 1) for _ in range(m + 1)]Create dp table for all prefixes of s and p

dp[0][0] = TrueEmpty pattern matches empty string

if p[j - 1] == '*': dp[0][j] = dp[0][j - 1]'*' can match empty string prefix

dp[i][j] = dp[i][j - 1] or dp[i - 1][j]'*' matches empty or one more char

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 1];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (p.charAt(j - 1) == '?' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isMatch("adceb", "*a*b")); // true
        System.out.println(sol.isMatch("aa", "a"));       // false
    }
}

Line Notes

boolean[][] dp = new boolean[m + 1][n + 1];DP table for prefix matches

dp[0][0] = true;Empty pattern matches empty string

if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 1];Handle '*' matching empty prefix

dp[i][j] = dp[i][j - 1] || dp[i - 1][j];'*' matches empty or one more char

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') dp[0][j] = dp[0][j - 1];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (p[j - 1] == '?' || p[j - 1] == s[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

int main() {
    Solution sol;
    cout << boolalpha << sol.isMatch("adceb", "*a*b") << endl; // true
    cout << boolalpha << sol.isMatch("aa", "a") << endl;       // false
    return 0;
}

Line Notes

vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));DP table initialization

dp[0][0] = true;Empty pattern matches empty string

if (p[j - 1] == '*') dp[0][j] = dp[0][j - 1];Handle '*' matching empty prefix

dp[i][j] = dp[i][j - 1] || dp[i - 1][j];'*' matches empty or one more char

function isMatch(s, p) {
    const m = s.length, n = p.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(false));
    dp[0][0] = true;
    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') dp[0][j] = dp[0][j - 1];
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            } else if (p[j - 1] === '?' || p[j - 1] === s[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
}

// Example usage
console.log(isMatch('adceb', '*a*b')); // true
console.log(isMatch('aa', 'a'));       // false

Line Notes

const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(false));Initialize 2D dp array

dp[0][0] = true;Empty pattern matches empty string

if (p[j - 1] === '*') dp[0][j] = dp[0][j - 1];Handle '*' matching empty prefix

dp[i][j] = dp[i][j - 1] || dp[i - 1][j];'*' matches empty or one more char

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We fill a 2D table of size (m+1)*(n+1) once.

💡 For strings of length 1000, this means 1 million table entries, which is efficient.

Interview Verdict: Accepted

Tabulation is a standard DP approach that is often preferred for clarity and iterative control.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i][j] depends only on dp[i-1][j-1], dp[i][j-1], and dp[i-1][j], we can optimize space by using two 1D arrays.

Intuition

Use two arrays to represent previous and current rows, updating iteratively to save memory.

Algorithm

1. Initialize two 1D arrays prev and curr of length n+1.
2. Set prev[0] = true for empty pattern and string.
3. Pre-fill prev for patterns starting with '*' matching empty string.
4. Iterate over s, update curr based on prev and pattern chars, then swap prev and curr.

💡 Backward iteration on pattern indices is needed to avoid overwriting dp values prematurely.

Recurrence:dp[j] = (p[j-1] == '*') ? dp[j] or dp[j-1] : (p[j-1] == s[i-1] or p[j-1] == '?') and prev[j-1]

</>

Code

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    prev = [False] * (n + 1)
    prev[0] = True
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            prev[j] = prev[j - 1]
    for i in range(1, m + 1):
        curr = [False] * (n + 1)
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                curr[j] = curr[j - 1] or prev[j]
            elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:
                curr[j] = prev[j - 1]
        prev = curr
    return prev[n]

# Example usage
if __name__ == '__main__':
    print(isMatch('adceb', '*a*b'))  # True
    print(isMatch('aa', 'a'))       # False

Line Notes

prev = [False] * (n + 1)Initialize dp array for previous row

prev[0] = TrueEmpty pattern matches empty string

if p[j - 1] == '*': prev[j] = prev[j - 1]Pre-fill for '*' matching empty string

curr[j] = curr[j - 1] or prev[j]'*' matches empty or one more char

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[] prev = new boolean[n + 1];
        prev[0] = true;
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') prev[j] = prev[j - 1];
        }
        for (int i = 1; i <= m; i++) {
            boolean[] curr = new boolean[n + 1];
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    curr[j] = curr[j - 1] || prev[j];
                } else if (p.charAt(j - 1) == '?' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    curr[j] = prev[j - 1];
                }
            }
            prev = curr;
        }
        return prev[n];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isMatch("adceb", "*a*b")); // true
        System.out.println(sol.isMatch("aa", "a"));       // false
    }
}

Line Notes

boolean[] prev = new boolean[n + 1];Previous row dp array

prev[0] = true;Empty pattern matches empty string

if (p.charAt(j - 1) == '*') prev[j] = prev[j - 1];Pre-fill for '*' matching empty string

curr[j] = curr[j - 1] || prev[j];'*' matches empty or one more char

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<bool> prev(n + 1, false);
        prev[0] = true;
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') prev[j] = prev[j - 1];
        }
        for (int i = 1; i <= m; i++) {
            vector<bool> curr(n + 1, false);
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    curr[j] = curr[j - 1] || prev[j];
                } else if (p[j - 1] == '?' || p[j - 1] == s[i - 1]) {
                    curr[j] = prev[j - 1];
                }
            }
            prev = curr;
        }
        return prev[n];
    }
};

int main() {
    Solution sol;
    cout << boolalpha << sol.isMatch("adceb", "*a*b") << endl; // true
    cout << boolalpha << sol.isMatch("aa", "a") << endl;       // false
    return 0;
}

Line Notes

vector<bool> prev(n + 1, false);Previous row dp array

prev[0] = true;Empty pattern matches empty string

if (p[j - 1] == '*') prev[j] = prev[j - 1];Pre-fill for '*' matching empty string

curr[j] = curr[j - 1] || prev[j];'*' matches empty or one more char

function isMatch(s, p) {
    const m = s.length, n = p.length;
    let prev = Array(n + 1).fill(false);
    prev[0] = true;
    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') prev[j] = prev[j - 1];
    }
    for (let i = 1; i <= m; i++) {
        let curr = Array(n + 1).fill(false);
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '*') {
                curr[j] = curr[j - 1] || prev[j];
            } else if (p[j - 1] === '?' || p[j - 1] === s[i - 1]) {
                curr[j] = prev[j - 1];
            }
        }
        prev = curr;
    }
    return prev[n];
}

// Example usage
console.log(isMatch('adceb', '*a*b')); // true
console.log(isMatch('aa', 'a'));       // false

Line Notes

let prev = Array(n + 1).fill(false);Previous row dp array

prev[0] = true;Empty pattern matches empty string

if (p[j - 1] === '*') prev[j] = prev[j - 1];Pre-fill for '*' matching empty string

curr[j] = curr[j - 1] || prev[j];'*' matches empty or one more char

⏱

Complexity

TimeO(m*n)

SpaceO(n)

Only two 1D arrays of length n+1 are used, reducing space from O(m*n) to O(n).

💡 For large strings, this saves significant memory while maintaining speed.

Interview Verdict: Accepted

Space optimization is a valuable skill to demonstrate in interviews, showing mastery of DP.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoization or tabulation are best for interviews; brute force is only for explanation; space optimization is bonus.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(m+n))	O(m+n)	Yes (deep recursion)	N/A	Mention only - never code
2. Top-Down DP with Memoization	O(m*n)	O(m*n)	Possible but less likely	Yes	Good for initial coding
3. Bottom-Up DP (Tabulation)	O(m*n)	O(m*n)	No	Yes	Preferred for clarity
4. Space Optimized Bottom-Up DP	O(m*n)	O(n)	No	No (without extra work)	Bonus if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and wildcard definitions.State brute force recursive approach to show problem complexity.Introduce memoization to optimize recursion.Explain bottom-up DP tabulation for iterative clarity.Discuss space optimization if time permits.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of recursion, memoization, DP table construction, handling of '*' wildcard, and space optimization.

Common Follow-ups

• How to handle multiple consecutive '*' efficiently → preprocess pattern to merge '*'
• Can you optimize space usage → use 1D dp arrays with careful iteration

💡 These follow-ups test deeper understanding of pattern preprocessing and DP space optimization.

🔍

Pattern Recognition

When to Use

1) Problem involves matching strings with wildcards; 2) '?' matches single char; 3) '*' matches any sequence; 4) Need full string match.

Signature Phrases

'?' matches any single character'*' matches any sequence of characters

NOT This Pattern When

Simple substring search or regex matching with complex operators

Similar Problems

Regular Expression Matching - similar but with '.' and '+' operatorsLongest Common Subsequence - foundational string DP pattern

Practice

1. Consider the following Python function implementing the space-optimized DP for Minimum ASCII Delete Sum:

def minimumDeleteSum(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [0] * (n + 1)
    for j in range(1, n + 1):
        dp[j] = dp[j-1] + ord(s2[j-1])
    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] += ord(s1[i-1])
        for j in range(1, n + 1):
            temp = dp[j]
            if s1[i-1] == s2[j-1]:
                dp[j] = prev
            else:
                dp[j] = min(dp[j] + ord(s1[i-1]), dp[j-1] + ord(s2[j-1]))
            prev = temp
    return dp[n]

print(minimumDeleteSum("sea", "eat"))

What is the final returned value for input s1 = "sea" and s2 = "eat"?

easy

A. 231

B. 197

C. 314

D. 259

Solution

1. Step 1: Initialize dp array for s2="eat"

   dp after first loop: dp=[0, 101('e'), 101+97('a')=198, 198+116('t')=314]

2. Step 2: Iterate over s1="sea" updating dp

   After processing 's': dp=[115, 101, 198, 314] After 'e': dp=[216, 115, 198, 314] After 'a': dp final dp[n]=231

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known example output 231 [OK]

Hint: Trace dp array updates carefully for each character [OK]

Common Mistakes:

• Off-by-one errors in indexing dp or strings

2. Consider the following code snippet implementing the bottom-up DP solution for Word Break II. Given s = "catsanddog" and wordDict = ["cat", "cats", "and", "sand", "dog"], what is the value of dp[3] after the outer loop iteration where i = 3 completes?

easy

A. ["and dog"]

B. ["and", "sand"]

C. ["dog"]

D. ["sand dog"]

Solution

1. Step 1: Identify substring starting at index 3

   Substring s[3:] = "sanddog". Check which words in dictionary start at index 3: "sand" matches.

2. Step 2: Build dp[3]

   For word "sand" (length 4), dp[3 + 4] = dp[7] contains ["dog"]. Append "sand" + " " + "dog" -> "sand dog" to dp[3]. No other words match at index 3.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   dp[3] = ["sand dog"] after iteration i=3 [OK]

Hint: Check substring matches and dp lookup carefully [OK]

Common Mistakes:

• Confusing index offsets or missing concatenation spaces

3. What is the time complexity of the space-optimized bottom-up DP solution for regular expression matching with input string length m and pattern length n?

medium

A. O(2^(m + n)) exponential due to backtracking

B. O(m + n) linear in combined length

C. O(m * n) due to nested iteration over string and pattern

D. O(n^2) quadratic in pattern length only

Solution

1. Step 1: Identify loops in the DP solution

   The outer loop iterates over the string length m, and the inner loop iterates over the pattern length n.

2. Step 2: Calculate total operations

   Each iteration of the outer loop runs the inner loop fully, resulting in m * n operations.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP table of size m by n is filled once [OK]

Hint: Nested loops over m and n imply O(m*n) time [OK]

Common Mistakes:

• Confusing exponential backtracking with DP complexity

4. Suppose you want to count the number of distinct subsequences of t in s, but now characters in s can be reused multiple times (i.e., you can use the same character in s multiple times to form subsequences). Which modification to the DP approach correctly solves this variant?

hard

A. Use a 2D DP where dp[i][j] counts subsequences using first i chars of s and j chars of t, but allow reusing s[i] by not incrementing i on match

B. Change the recurrence to allow staying at the same i index when matching characters

C. Use the same DP but iterate j forward instead of backward in the inner loop

D. No change needed; original DP already counts subsequences with reuse

Solution

1. Step 1: Understand reuse means characters in s can be used multiple times

   Original DP assumes each character in s can be used at most once per subsequence.

2. Step 2: Modify DP to allow reusing s[i]

   Use 2D DP where dp[i][j] counts subsequences using first i chars of s for first j chars of t, and when s[i] matches t[j], allow staying at i (not incrementing) to reuse character.

3. Step 3: Recognize that iterating j forward or no change won't handle reuse correctly

   Only explicit state allowing reuse by not advancing i on match works.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Allowing reuse requires 2D DP with careful state transitions [OK]

Hint: Reuse means allowing same s[i] multiple times, so must not always increment i

Common Mistakes:

• Assuming original DP handles reuse
• Trying to fix by changing iteration order only

5. Suppose you want to compute the edit distance where characters can be replaced multiple times (reuse allowed) and the cost of replacement depends on character pairs. Which modification to the classic DP approach correctly handles this variant?

hard

A. Use bottom-up DP with a cost matrix for replacements and update dp accordingly

B. Modify DP to allow revisiting states multiple times with memoization

C. Switch to a greedy approach that picks cheapest replacement at each mismatch

D. Use the same DP but add a third dimension for replacement cost per character pair

Solution

1. Step 1: Understand replacement cost depends on character pairs

   Replacement cost varies, so DP must incorporate a cost matrix for each character pair.

2. Step 2: Adapt bottom-up DP to use cost matrix in dp updates

   When characters differ, dp[j] updates using the specific replacement cost from the matrix, ensuring correct minimal cost.

3. Step 3: Confirm approach handles reuse and varying costs

   Bottom-up DP with cost matrix correctly accumulates minimal costs allowing multiple replacements.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP with cost matrix handles variable replacement costs [OK]

Hint: Incorporate cost matrix into DP transitions for variable replacements [OK]

Common Mistakes:

• Adding extra DP dimension unnecessarily
• Using memoization without cost matrix
• Trying greedy which fails globally