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:

1
2
3

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

Example 2:

1
2
3

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

Example 3:

1
2
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

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

Examples for Leetcode 10

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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)