HardStringDynamic ProgrammingGreedy

Wildcard Matching

1 approach, code in every language

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 see the solution

You get 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

After the pattern

Now solve one you haven't seen.

Dispatch Rule Match is our own problem on the technique behind Wildcard Matching: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free