HardStringDynamic ProgrammingGreedy

Wildcard Matching

1 approach, code in all languages

You are given a text string and a pattern string. The pattern may contain a question mark '?' that matches exactly one arbitrary character and a star '*' that matches any run of characters, including an empty run. Return whether the pattern matches the entire text.

Unlike some other matching rules, here a star stands on its own and can absorb any number of characters, which makes it a flexible gap in the pattern.

Example 1

Input: s = "cat", p = "c?t"

Output: true

The '?' matches the single character 'a', so the pattern lines up with the text.

Example 2

Input: s = "cat", p = "c*b"

Output: false

The star can absorb "at", but the trailing "b" cannot be matched, so the whole pattern fails.

Constraints

0 ≤ s.length ≤ 2 * 10^3
0 ≤ p.length ≤ 2 * 10^3
s contains only lowercase English letters
p contains lowercase letters, '?', and '*'

Bottom-up 2D DP

Fill a table dp[i][j] meaning the first i text characters match the first j pattern characters, using the star's ability to match empty or one-more.

Loading animation…

Intuition

A star is the only symbol that breaks a one-to-one alignment, so the recurrence hinges on it. When the pattern position is a star, either the star matches nothing and we lean on dp[i][j-1], or it soaks up the current text character and we lean on dp[i-1][j]. Every other symbol demands an exact or wildcard single-character match, inheriting the diagonal cell. Seeding the empty-text row lets leading stars match nothing before real work begins.

Algorithm walkthrough

1Allocate dp of size (m+1) x (n+1), all false, and set dp[0][0] = true for two empty strings.
2Fill the first row: dp[0][j] stays true only while every pattern character up to j is a star, since a star can match an empty text.
3For a normal character or '?', require the diagonal dp[i-1][j-1] to hold and the characters to be compatible.
4For a star, set dp[i][j] to dp[i-1][j] OR dp[i][j-1], covering matching one more text character or matching nothing.
5Return dp[m][n] as the verdict for the full text against the full pattern.

Implementation

class Solution:
    def isMatch(self, 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 - 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[m][n]

Time

O(m * n)

Space

O(m * n)

Each of the (m+1) x (n+1) cells is computed once; a rolling two-row array can shrink space to O(n).

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI