Problem statement

Implement wildcard pattern matching over the whole string:

• ? matches any single character.
• * matches any sequence of characters, including the empty sequence.

Return true if p matches all of s.

Example 1

Input: s = "aa", p = "a"
Output: false
Explanation: The pattern must cover the entire string.

Example 2

Input: s = "aa", p = "*"
Output: true

Example 3

Input: s = "cb", p = "?a"
Output: false
Explanation: ? matches c, but a does not match b.

Constraints

• 0 <= s.length, p.length <= 2000
• s consists of lowercase English letters.
• p consists of lowercase English letters, '?' and '*'.

Hints for Wildcard Matching

1. Hint 1

   dp[i][j] = does p[0..j) match s[0..i)?

2. Hint 2

   A * either consumes one more character of s (dp[i-1][j]) or matches nothing (dp[i][j-1]).

3. Hint 3

   The first row needs care: a pattern of only stars matches the empty string.

How to solve Wildcard Matching

A two-dimensional boolean table over prefixes. The only branching character is *, which contributes exactly two transitions.

Approach

1. Set dp[0][0] = true; the empty pattern matches the empty string.
2. Fill row 0: dp[0][j] = dp[0][j-1] when p[j-1] is *, otherwise false.
3. For each cell: if the pattern character is *, dp[i][j] = dp[i-1][j] || dp[i][j-1].
4. If it is ? or equals s[i-1], dp[i][j] = dp[i-1][j-1].
5. Otherwise leave it false. Return dp[n][m].

Why it works

dp[i-1][j] means the star has already absorbed some characters and takes one more; dp[i][j-1] means the star absorbs nothing. Every other pattern character consumes exactly one string character, so it steps diagonally.

Complexity

• Time — O(n · m)
• Space — O(n · m), reducible to O(m)

Pitfalls

• Forgetting the row-0 star handling rejects s = "" with p = "***".
• Treating * like the regex * (which applies to the preceding character) is a different problem entirely — here it stands alone.
• A greedy two-pointer solution with backtracking also works and is O(1) space, but is much easier to get wrong.

Reference solution

Python

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

Java

public static boolean isMatch(String s, String p) {
    int n = s.length(), m = p.length();
    boolean[][] dp = new boolean[n + 1][m + 1];
    dp[0][0] = true;
    for (int j = 1; j <= m; j++) {
        if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 1];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char pc = p.charAt(j - 1);
            if (pc == '*') dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            else if (pc == '?' || pc == s.charAt(i - 1)) dp[i][j] = dp[i - 1][j - 1];
        }
    }
    return dp[n][m];
}

C++

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

JavaScript

var isMatch = function(s, p) {
    const n = s.length, m = p.length;
    const dp = [];
    for (let i = 0; i <= n; i++) dp.push(new Array(m + 1).fill(false));
    dp[0][0] = true;
    for (let j = 1; j <= m; j++) {
        if (p.charAt(j - 1) === "*") dp[0][j] = dp[0][j - 1];
    }
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            const pc = p.charAt(j - 1);
            if (pc === "*") dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            else if (pc === "?" || pc === s.charAt(i - 1)) dp[i][j] = dp[i - 1][j - 1];
        }
    }
    return dp[n][m];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard