Problem 31.9 · DP on Strings and SequencesHard

Wildcard Matching

What it teaches: A star matches empty (move in the pattern) or one more character (move in the string).

Practise it on judges as “Wildcard Matching”.

The problem

? matches any single character and * matches any sequence (including empty). Return true if pattern p matches the whole string s.

Example 1

Input: s = "adceb", p = "*a*b"
Output: true

Example 2

Input: s = "cb", p = "?a"
Output: false

Constraints

0 ≤ lengths ≤ 2000

Pattern clues in the wording

→ Pattern with wildcards against a whole string

These clues point to DP on Two Strings: dp[i][j] answers the question for the first i characters of one string and the first j of the other.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public boolean isMatch(String s, String p) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	s = "aa" p = "a"	false
2	s = "aa" p = "*"	true
3	s = "cb" p = "?a"	false
4	s = "adceb" p = "ab"	true

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. 2D DP · O(m × n)

2D DP

Time O(m × n) Space O(m × n)

dp[0][0] = true; dp[0][j] true while p is all stars. Fill with the three rules.

Approach 1

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 && p.charAt(j - 1) == '*'; j++) dp[0][j] = true;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                char pc = p.charAt(j - 1);
                if (pc == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                else dp[i][j] = (pc == '?' || pc == s.charAt(i - 1)) && dp[i - 1][j - 1];
            }
        return dp[m][n];
    }
}

Verdict: Correct and clear.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty pattern
Pattern of only stars
Empty string

Mistakes people make

Treating '*' like regex ("zero or more of the previous character") instead of "any sequence".

Interview

Follow-up questions

What's different in Regular Expression Matching?

Command Palette

The problem

Approaches

2D DP

Edge cases and common mistakes

Follow-up questions