Wildcard Matching Pattern

Wildcard Matching is a pattern matching algorithm that checks whether a given input string matches a specified pattern that may contain wildcards. Wildcards are special characters that can represent one or more characters in a string. In most wildcard matching problems, the two most common wildcard characters are:

  • * (asterisk): Matches zero or more characters.
  • ? (question mark): Matches exactly one character.

The problem of Wildcard Matching is widely used in file systems for searching files by name and in string processing applications. The goal is to determine if a string (referred to as the input string) matches a pattern that contains these special wildcard characters.

Input-Output Examples

plaintext
Example 1:
Input: s = "abcdef", p = "a*d*f"
Output: True
Explanation: The * wildcard matches "bcde", a
nd the string "abcdef" matches the pattern "a*d*f".

Example 2:
Input: s = "abcdef", p = "a*c?f"
Output: False
Explanation: The ? wildcard matches exactly 
one character, but "c?f" does not match "bcdef".

How Wildcard Matching Works ?

The Wildcard Matching problem is typically solved using dynamic programming or backtracking. In both approaches, the goal is to match each character of the input string with the corresponding character in the pattern, while appropriately handling the wildcard characters.

Step-by-step explanation:

  1. Exact Match: If the current character in the pattern is a regular character (neither * nor ?), it must exactly match the corresponding character in the input string.
  2. Single Character Match (**?**): If the pattern contains ?, it can match exactly one character in the input string.
  3. Zero or More Characters Match (*****): If the pattern contains *, it can match zero or more characters in the input string. This means the * can be treated as an empty sequence, or it can match one or more characters.

Algorithm

Here’s a general approach to solve Wildcard Matching using dynamic programming:

  1. Create a 2D boolean table where dp[i][j] is True if the first i characters of the input string match the first j characters of the pattern.
  2. Base Case: dp[0][0] is True because an empty pattern matches an empty string.
  3. Fill the DP Table:
    • If the current character in the pattern is a regular character or ?, set dp[i][j] based on whether dp[i-1][j-1] is True.
    • If the current character in the pattern is *, it can match zero or more characters. Thus, set dp[i][j] to True if either dp[i][j-1] (matching zero characters) or dp[i-1][j] (matching one or more characters) is True.
  4. Result: The final result will be stored in dp[n][m] where n is the length of the input string and m is the length of the pattern.

Example of Wildcard Matching

Let’s take an example where the input string is "abefcdgiescdfimde" and the pattern is "ab*cd?i*de":

  • Input String: "abefcdgiescdfimde"
  • Pattern: "ab*cd?i*de"

Explanation:

  1. The pattern starts with "ab" which exactly matches the beginning of the input string.
  2. The * wildcard matches any sequence of characters, so it can match "ef".
  3. The next characters "cd" match "cd" in the input string.
  4. The ? wildcard matches exactly one character, which matches "g".
  5. The characters "i" match in both the pattern and input string.
  6. The second * wildcard can match "escdfim".
  7. The final "de" in the pattern matches "de" in the input string.

Therefore, the input string matches the pattern.

C++ Program to implement Wildcard Matching Pattern

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to check if the input string matches the pattern
bool isMatch(string s, string p) {
    int n = s.length();
    int m = p.length();
    
    // Create a 2D DP table with (n+1)x(m+1) dimensions
    vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));

    // Base case: Empty pattern matches empty string
    dp[0][0] = true;

    // Fill the first row (when the string is empty)
    for (int j = 1; j <= m; j++) {
        if (p[j - 1] == '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }

    // Fill the DP table
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (p[j - 1] == '?' || p[j - 1] == s[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1];  // Match one character
            } else if (p[j - 1] == '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];  // Match zero or more characters
            }
        }
    }

    return dp[n][m];
}

// Main function
int main() {
    string s = "abefcdgiescdfimde";
    string p = "ab*cd?i*de";
    
    if (isMatch(s, p)) {
        cout << "The pattern matches the string." << endl;
    } else {
        cout << "The pattern does not match the string." << endl;
    }

    return 0;
}

Java Program to implement Wildcard Matching Pattern

java
public class Main {
    // Function to check if the input string matches the pattern
    public static boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        
        // Create a 2D DP table with (n+1)x(m+1) dimensions
        boolean[][] dp = new boolean[n + 1][m + 1];

        // Base case: Empty pattern matches empty string
        dp[0][0] = true;

        // Fill the first row (when the string is empty)
        for (int j = 1; j <= m; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }

        // Fill the DP table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p.charAt(j - 1) == '?' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];  // Match one character
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];  // Match zero or more characters
                }
            }
        }

        return dp[n][m];
    }

    // Main function
    public static void main(String[] args) {
        String s = "abefcdgiescdfimde";
        String p = "ab*cd?i*de";
        
        if (isMatch(s, p)) {
            System.out.println("The pattern matches the string.");
        } else {
            System.out.println("The pattern does not match the string.");
        }
    }
}

Python Program to implement Wildcard Matching Pattern

python
# Function to check if the input string matches the pattern
def is_match(s, p):
    n = len(s)
    m = len(p)
    
    # Create a 2D DP table with (n+1)x(m+1) dimensions
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    
    # Base case: Empty pattern matches empty string
    dp[0][0] = True
    
    # Fill the first row (when the string is empty)
    for j in range(1, m + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]
    
    # Fill the DP table
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if p[j - 1] == '?' or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # Match one character
            elif p[j - 1] == '*':
                dp[i][j] = dp[i - 1][j] or dp[i][j - 1]  # Match zero or more characters
    
    return dp[n][m]

# Main function
if __name__ == "__main__":
    s = "abefcdgiescdfimde"
    p = "ab*cd?i*de"
    
    if is_match(s, p):
        print("The pattern matches the string.")
    else:
        print("The pattern does not match the string.")

Properties of Wildcard Matching

  • Time Complexity: The time complexity of the dynamic programming approach is O(n * m), where n is the length of the input string and m is the length of the pattern.
  • Space Complexity: The space complexity is also O(n * m) due to the 2D DP table.

When to Use Wildcard Matching ?

Wildcard Matching is useful in scenarios like:

  • File searching: When searching for files in a directory, wildcards like * and ? can be used to specify flexible search patterns (e.g., *.txt to match all text files).
  • String pattern matching: When dealing with strings that need flexible matching criteria, such as partial string matching or searching for substrings with unknown lengths.

DSA

4073

815

Related Articles