How Do You Implement Wildcard Pattern Matching?

Wildcard pattern matching is a common problem in programming and is often asked in technical interviews. It involves checking if a given string matches a pattern that includes special characters, typically ? and *. The ? wildcard matches any single character, while the * wildcard matches any sequence of characters, including an empty sequence. Understanding how to implement this efficiently is valuable as it tests your ability to handle string manipulations, dynamic programming, and algorithmic thinking.

Problem Explanation

Suppose you have a string s and a pattern p. Your goal is to determine whether p matches s based on the rules of wildcards:

• ? matches any single character.
• * matches zero or more characters, including none.

For example:

• s = "abcde", p = "a*e" → True (because * can cover "bcd")
• s = "abcde", p = "a?c*" → True (because ? matches b, and * matches de)
• s = "abcde", p = "a*d" → False (since d does not match the last character e)

Common Approach: Dynamic Programming

One efficient way to solve this problem is through dynamic programming. The idea is to build up a table where each entry dp[i][j] indicates whether the substring s[:i] matches the pattern p[:j].

Algorithm Steps:

1. Initialize a 2D boolean array dp with dimensions (len(s)+1) x (len(p)+1).

2. Set dp to True because an empty pattern matches an empty string.

3. Fill the first row dp[j] considering patterns that can match an empty string (e.g., patterns with just *).

4. Loop through characters of s and p:

   • If the current pattern character p[j-1] is ?, then dp[i][j] = dp[i-1][j-1] because ? can match any single character.

   • If the pattern character is *, then dp[i][j] = dp[i][j-1] (assuming * matches zero characters) or dp[i-1][j] (assuming * matches one more character).

   • If the pattern character is a normal character, then dp[i][j] = (s[i-1] == p[j-1]) and dp[i-1][j-1].

5. The answer will be in dp[len(s)][len(p)].

Example Code:

PythonCopy code

Example Run:

PythonCopy code

Key Points:

• The dynamic programming approach ensures that each subproblem is solved only once, making it efficient.
• The dp table keeps track of all matches up to certain points, allowing for a systematic solution.
• Handling the * wildcard correctly is crucial because it can match a sequence of characters, which requires considering both zero and multiple character matches.

Practicing this pattern with different inputs and understanding how to initialize your dp table will help you handle many variations of wildcard matching questions in interviews.