problemhardalgorithmsleetcode-44leetcode 44leetcode44

Wildcard Matching

HardUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

  • '?' Matches any single character.
  • '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Examples

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Similar Problems

Leetcode 44 Vs Leetcode 10 OR [Regular Expression Matching](regular-expression-matching)

This problem look very similar to Leetcode 10. But actually it is slightly different.

Examples for Leetcode 10

isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true

Similar Examples for Leetcode 44 Aka Current Problem

isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "*") ? true
isMatch("aa", "a*") ? true
isMatch("aa", "?*") ? true
isMatch("aab", "c*a*b") ? false

Solution

Method 1 - Recursion

We have following cases in recursion:

  1. Base Case:
    • If we've reached the end of the pattern p (j == p.length()), the string s must also be fully matched (i == s.length()).
  2. Recursive Case:
    • If the current character in the pattern is '*', it can match zero or more characters from s:
      • isMatchHelper(s, p, i, j + 1): Considers '*' as matching zero characters.
      • isMatchHelper(s, p, i + 1, j): Considers '*' as matching one or more characters.
    • If the current character in the pattern is '?' or matches the current character in s:
      • Move to the next character in both s and p.

Code

Java
public class Solution {

	public boolean isMatch(String s, String p) {
		return isMatchHelper(s, p, 0, 0);
	}

	private boolean isMatchHelper(String s, String p, int i, int j) {
		if (j == p.length()) {
			return i == s.length();
		}

		if (p.charAt(j) == '*') {
			// '*' matches zero characters or matches one character and moves to next in s
			return isMatchHelper(s, p, i, j + 1) || (i < s.length() && isMatchHelper(s, p, i + 1, j));
		} else {
			// Match current character or '?'
			return i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?') && isMatchHelper(s, p, i + 1, j + 1);
		}
	}

}

Complexity

  • ⏰ Time complexity: O(2 ^ (m + n)), where m is length of s and n is length of p

    • Worst-Case Scenario can be that every character in the pattern is *. This results in two recursive calls for each character in the pattern, leading to exponential growth.
    • The total depth of the recursion tree can be up to the sum of the lengths of s and p because each step potentially moves forward either in s, p, or both.

  • 🧺 Space complexity: O(m + n), for using the recursion stack

Method 2 - Top Down DP with memoization

We can use a map to store results of subproblems, avoiding redundant computations with memoization, indexed by the string "i,j" where i is the current index in s and j is the current index in p.

Code

Java
public class Solution {

	public boolean isMatch(String s, String p) {
		Map<String, Boolean> memo = new HashMap<>();
		return isMatchHelper(s, p, 0, 0, memo);
	}

	private boolean isMatchHelper(String s, String p, int i, int j, Map<String, Boolean> memo) {
		String key = i + "," + j;

		if (memo.containsKey(key)) {
			return memo.get(key);
		}

		if (j == p.length()) {
			return i == s.length();
		}

		boolean result;

		if (p.charAt(j) == '*') {
			result = isMatchHelper(s, p, i, j + 1, memo) || (i < s.length() && isMatchHelper(s, p, i + 1, j, memo));
		} else {
			result = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?') && isMatchHelper(s, p, i + 1, j + 1, memo);
		}

		memo.put(key, result);
		return result;
	}

}

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(m*n)
    • for using memoization map - O(m*n),
    • for using recursion stack - O(m + n)

Method 3 - Bottom up DP

We can change the code to use bottom up DP. Here are the steps:

  1. Initialization:
    • Create a 2D boolean array dp with dimensions (m + 1) x (n + 1) where m is the length of the input string s and n is the length of the pattern p.
    • dp[i][j] represents if the first i characters of s match the first j characters of p.
  2. Base Case:
    • dp[0][0] is true because an empty string matches an empty pattern.
    • Handle the cases where the pattern starts with *, which can match an empty sequence.
  3. DP Table Filling:
    • Iterate over each character of s and p.
    • For each * in the pattern:
      • dp[i][j] becomes true if either:
        • The * matches zero characters (i.e., the previous state dp[i][j - 1]).
        • The * matches one or more characters (i.e., the previous state dp[i - 1][j]).
    • For each ? or exact character match:
      • dp[i][j] is set based on dp[i - 1][j - 1].
  4. Result:
    • The final result is stored in dp[m][n], indicating whether the entire input string s matches the pattern p.

Code

Java
public class Solution {

	public boolean isMatch(String s, String p) {
		int m = s.length();
		int n = p.length();
		// Initialize a 2D DP array
		boolean[][] dp = new boolean[m + 1][n + 1];

		// An empty pattern matches an empty string
		dp[0][0] = true;

		// Handle patterns with '*' that can match empty sequence
		for (int j = 1; j <= n; j++) {
			if (p.charAt(j - 1) == '*') {
				dp[0][j] = dp[0][j - 1];
			}
		}

		// Fill the DP table
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (p.charAt(j - 1) == '*') {
					// '*' can match any sequence (empty or non-empty)
					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)) {
					// '?' matches any single character
					// Characters must match for non-wildcards
					dp[i][j] = dp[i - 1][j - 1];
				}
			}
		}

		// The result is in the bottom-right corner of the DP table
		return dp[m][n];
	}
}

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(m*n)

Comments