44. Wildcard Matching


Problem Description

The problem is a classic example of pattern matching where we are given a string s and a pattern p that includes wildcard characters. We need to determine if the pattern p matches the entire string s. The wildcard characters are defined as follows:

  • A question mark ('?') matches any single character.
  • An asterisk ('*') matches any sequence of characters, including an empty sequence.

The goal is to check if there is a complete match between the entire string and the pattern, not just a partial match.

Intuition

For solving this problem, dynamic programming is a common approach because it allows us to break down the complex problem into smaller subproblems and then build up the solution from these.

The key insight is to realize that we can make a decision at each character in the string based on two conditions:

  1. If the current character in the pattern is a ? or matches the current character in the string, we refer to previous states where the match has been progressing without the current character and pattern.

  2. If the current character in the pattern is a *, it can be complex because * can match an empty sequence or any sequence of characters. We need to consider multiple cases: either we use the * to match zero characters in the string (which means we look at the state of the match without the *), or we use the * to match at least one character in the string (which means we look at the state of the match without the current character in the string, but keep the *).

This method of breaking down the problem helps us to derive a solution using a 2D matrix dp where dp[i][j] represents whether the first i characters of the string s can be matched with the first j characters of the pattern p. The final answer at dp[m][n] (where m and n are the lengths of the string and pattern respectively) gives us the answer to whether the entire string matches the pattern.

By filling up the matrix by iterating over the string and the pattern, we use the previously solved subproblems to inform the solution of the current subproblem. Eventually, we derive the solution to the entire problem.

Learn more about Greedy, Recursion and Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming, a method where complex problems are broken into simpler subproblems and solved individually, with the solutions to the subproblems stored to avoid redundant calculations.

Here is a breakdown of the implementation steps:

  1. Initialize a 2D matrix dp with dimensions (m + 1) x (n + 1), where m is the length of the string s and n is the length of the pattern p. Each element dp[i][j] in this matrix will store a boolean value indicating if s[0..i-1] matches p[0..j-1]. The +1 offset allows us to easily handle the empty string and pattern cases.

  2. Set the first element dp[0][0] to True to represent that an empty string matches an empty pattern.

  3. Pre-fill the first row of the matrix by setting dp[0][j] to True if p[j-1] is * and dp[0][j-1] is also True. This loop accounts for the situation where the pattern starts with one or multiple * characters, which can match the empty string.

    1for j in range(1, n + 1):
    2    if p[j - 1] == '*':
    3        dp[0][j] = dp[0][j - 1]
  4. Iterate through the matrix starting from i = 1 and j = 1, and calculate the dp[i][j] value based on the following rules:

    • If the current character of s[i - 1] matches the current character of p[j - 1] or p[j - 1] is a ? (which can match any single character), then set dp[i][j] to the value of dp[i - 1][j - 1] since we can carry forward the match status from previous characters.

      1if s[i - 1] == p[j - 1] or p[j - 1] == '?':
      2    dp[i][j] = dp[i - 1][j - 1]
    • If the current character of the pattern is *, there are two possibilities:

      • The * matches zero characters: carry forward the status from dp[i][j - 1].
      • The * matches one or more characters: carry forward the status from dp[i - 1][j].

    Hence:

    1 ```python
    2 elif p[j - 1] == '*':
    3     dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
    4 ```
    • For all other cases where characters don't match and there is no wildcard, dp[i][j] will remain False, which is the default value after initialization.
  5. After filling the entire matrix, the value at dp[m][n] will indicate whether the entire string s matches the pattern p.

This approach ensures that each subproblem is only calculated once and then reused, dramatically reducing the time complexity from exponential (which would be the case with a naive recursive approach) to polynomial time.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Example Walkthrough

Let's illustrate the solution approach using a small example:

Assume s = "xaabyc" and p = "*a?b*".

  1. Initialize the 2D matrix dp: Since s has a length of 6 and p has a length of 5, our matrix dp will be a 7x6 matrix (including the extra row and column for the empty string and pattern case). Initially, all values in dp are set to False.

  2. First element dp[0][0]: We set dp[0][0] to True to denote that an empty pattern matches an empty string.

  3. First row pre-fill: We then iterate over the first row of dp to account for a pattern that starts with *. In this case, p[0] is *, so dp[0][1] should be set to True. Following that logic, here's how the first row will look after pre-filling:

    *a?b*
    TTFFFF
  4. Iterate and fill the matrix:

    a. For i = 1 and j = 1, the pattern has * which matches zero characters from s. So, dp[1][1] is True because dp[0][0] was true.

    b. When j = 2 and i = 1, the pattern is a but our string is x. Since they don't match and the pattern is not a ?, dp[1][2] stays False.

    *a?b*
    TTFFFF
    xFTFFFF

    c. Eventually, by following the iteration rules while filling out the matrix, we will have:

    *a?b*
    TTFFFF
    xFTFFFF
    aFTTFFF
    aFTTTFF
    bFTFTTF
    yFTFFTT
    cFTFFFT
  5. Final Check: Our final cell dp[6][5] contains True. Therefore, we can deduce that with the given example, the string s matches the pattern p.

By processing the dp matrix according to the dynamic programming approach, we've avoided redundant calculations and determined the match between s and p efficiently.

Solution Implementation

1class Solution:
2    def isMatch(self, string: str, pattern: str) -> bool:
3        # Get the lengths of the input string and the pattern
4        length_s, length_p = len(string), len(pattern)
5      
6        # Create a DP table with default values False
7        dp = [[False] * (length_p + 1) for _ in range(length_s + 1)]
8      
9        # The empty pattern matches the empty string
10        dp[0][0] = True
11      
12        # Initialize first row of the DP table, considering the pattern starting with '*'
13        for j in range(1, length_p + 1):
14            if pattern[j - 1] == '*':
15                dp[0][j] = dp[0][j - 1]
16      
17        # Fill the DP table
18        for i in range(1, length_s + 1):
19            for j in range(1, length_p + 1):
20                # If characters match or pattern has '?', we can move back diagonally in the table (match found)
21                if string[i - 1] == pattern[j - 1] or pattern[j - 1] == '?':
22                    dp[i][j] = dp[i - 1][j - 1]
23                # If pattern has '*', we check two cases:
24                # 1. '*' matches no character: move left in the table
25                # 2. '*' matches at least one character: move up in the table
26                elif pattern[j - 1] == '*':
27                    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
28
29        # Return the value at the bottom-right corner of the DP table
30        return dp[length_s][length_p]
31
1class Solution {
2  
3    public boolean isMatch(String str, String pattern) {
4        // Lengths of the input string and the pattern
5        int strLen = str.length(), patternLen = pattern.length();
6      
7        // dp[i][j] will be true if the first i characters in given string
8        // match the first j characters of the pattern
9        boolean[][] dp = new boolean[strLen + 1][patternLen + 1];
10      
11        // Empty string and empty pattern are a match
12        dp[0][0] = true;
13      
14        // Initialize the first row for the cases where pattern contains *
15        // as they can match the empty string
16        for (int j = 1; j <= patternLen; ++j) {
17            if (pattern.charAt(j - 1) == '*') {
18                dp[0][j] = dp[0][j - 1];
19            }
20        }
21      
22        // Build the dp matrix in bottom-up manner
23        for (int i = 1; i <= strLen; ++i) {
24            for (int j = 1; j <= patternLen; ++j) {
25                // If the current characters match or pattern has '?',
26                // we can propagate the diagonal value
27                if (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '?') {
28                    dp[i][j] = dp[i - 1][j - 1];
29                }
30                // If pattern contains '*', it can either match zero characters
31                // in the string or it can match one character in the string
32                // and continue matching
33                else if (pattern.charAt(j - 1) == '*') {
34                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
35                }
36                // If the current pattern character is not a wildcard and the characters
37                // don't match, dp[i][j] remains false, which is the default value.
38            }
39        }
40      
41        // The value in the bottom right corner will be our answer
42        return dp[strLen][patternLen];
43    }
44}
45
1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    bool isMatch(const std::string& s, const std::string& p) {
7        int strSize = s.size(), patternSize = p.size();
8        // Create a DP table with dimensions (m+1) x (n+1) initialized to false.
9        // dp[i][j] will be true if the first i characters of s match the first j
10        // characters of p.
11        std::vector<std::vector<bool>> dp(strSize + 1, std::vector<bool>(patternSize + 1, false));
12      
13        // The empty pattern matches the empty string.
14        dp[0][0] = true;
15      
16        // Initialize the first row of the DP table. If we find '*', it can match 
17        // an empty string, which is the state of dp[0][j-1].
18        for (int j = 1; j <= patternSize; ++j) {
19            if (p[j - 1] == '*') {
20                dp[0][j] = dp[0][j - 1];
21            }
22        }
23      
24        // Fill the DP table.
25        for (int i = 1; i <= strSize; ++i) {
26            for (int j = 1; j <= patternSize; ++j) {
27                // If the characters match or the pattern character is '?',
28                // we can transition from the state dp[i-1][j-1].
29                if (s[i - 1] == p[j - 1] || p[j - 1] == '?') {
30                    dp[i][j] = dp[i - 1][j - 1];
31                } 
32                // If the pattern character is '*', it can either match zero characters,
33                // meaning we transition from dp[i][j-1], or it can match one character,
34                // meaning we transition from dp[i-1][j].
35                else if (p[j - 1] == '*') {
36                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
37                }
38            }
39        }
40      
41        // The final state dp[m][n] gives us the answer to whether the entire
42        // strings s and p match with each other.
43        return dp[strSize][patternSize];
44    }
45};
46
1function isMatch(s: string, p: string): boolean {
2    let strLen: number = s.length;
3    let patternLen: number = p.length;
4
5    // Create a DP table with dimensions (strLen+1) x (patternLen+1) initialized to false.
6    // dp[i][j] will be true if the first i characters of s match the first j characters of p.
7    let dp: boolean[][] = Array.from({ length: strLen + 1 }, 
8                                     () => Array<boolean>(patternLen + 1).fill(false));
9
10    // The empty pattern matches the empty string.
11    dp[0][0] = true;
12
13    // Initialize the first row of the DP table. If we find '*', it can match
14    // an empty string, thereby adopting the value from dp[0][j-1].
15    for (let j = 1; j <= patternLen; j++) {
16        if (p[j - 1] === '*') {
17            dp[0][j] = dp[0][j - 1];
18        }
19    }
20
21    // Fill the DP table.
22    for (let i = 1; i <= strLen; i++) {
23        for (let j = 1; j <= patternLen; j++) {
24            // If the characters match or the pattern character is '?',
25            // we can transition from the state dp[i-1][j-1].
26            if (s[i - 1] === p[j - 1] || p[j - 1] === '?') {
27                dp[i][j] = dp[i - 1][j - 1];
28            }
29            // If the pattern character is '*', it can either match zero characters,
30            // meaning we transition from dp[i][j-1], or it can match one or more characters,
31            // meaning we transition from dp[i-1][j].
32            else if (p[j - 1] === '*') {
33                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
34            }
35        }
36    }
37
38    // The final state dp[strLen][patternLen] gives us the answer to whether the entire
39    // strings s and p match with each other.
40    return dp[strLen][patternLen];
41}
42

Time and Space Complexity

The time complexity of the provided code is O(m * n), where m is the length of the string s and n is the length of the pattern p. This is because the code involves a nested loop structure that iterates through the lengths of s and p. Each cell in the DP table dp[i][j] computes whether the first i characters of s match the first j characters of p, and the computation of each cell is constant time.

The space complexity of the code is also O(m * n). This is due to the use of a two-dimensional list dp, which has (m + 1) * (n + 1) elements, to store the states of substring matches. Each element of this list represents a subproblem, with extra rows and columns to handle empty strings.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄