Wildcard Matching In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
A close-up shot of a person coding on a laptop, focusing on the hands and screen.

Wildcard Matching Problem

In the Wildcard Matching problem, you are given two strings: a text string s and a pattern string p. The pattern string contains two special characters:

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

The goal is to determine if the pattern p matches the entire string s.

Problem Statement:

Given a string s and a pattern p, return true if p matches s, and false otherwise.

Examples:

Example 1:

Input: s = "aa", p = "a*"
Output: true
Explanation: The pattern "a*" matches the entire string "aa".

Example 2:

Input: s = "cb", p = "?a"
Output: false
Explanation: The pattern "?a" does not match the string "cb".

Example 3:

Input: s = "adceb", p = "*a*b"
Output: true
Explanation: The pattern "*a*b" matches the string "adceb".

Example 4:

Input: s = "acdcb", p = "a*c?b"
Output: false
Explanation: The pattern "a*c?b" does not match the string "acdcb".

Approach:

We can solve this problem using Dynamic Programming (DP).

Key Observations:

  1. The character '*' can match zero or more characters, so it requires a special treatment.
  2. The character '?' matches exactly one character, so it behaves like a regular character but with an automatic match for any single character.
  3. We need to check every possible combination of how the pattern p can match the string s considering the wildcard characters.

Dynamic Programming Approach:

We can create a DP table dp[i][j] where:

  • i represents the first i characters of the string s.
  • j represents the first j characters of the pattern p.

The value dp[i][j] will be true if the substring s[0...i-1] matches the pattern p[0...j-1].

Base Cases:

  • dp[0][0] = true: An empty string matches an empty pattern.
  • dp[i][0] = false for all i > 0: An empty pattern cannot match a non-empty string.
  • dp[0][j] = true if the pattern consists of only '*' characters up to j. Otherwise, it is false.

Recurrence Relation:

  • If p[j-1] == '?' or p[j-1] == s[i-1], then dp[i][j] = dp[i-1][j-1].
  • If p[j-1] == '*', then:
    • dp[i][j] = dp[i-1][j] (i.e., treat '*' as matching one more character in s).
    • dp[i][j] = dp[i][j-1] (i.e., treat '*' as matching zero characters in s).

Time and Space Complexity:

  • Time Complexity: O(m * n), where m is the length of string s and n is the length of pattern p. We are filling a 2D DP table of size m x n.
  • Space Complexity: O(m * n) for the DP table.

Code Implementations:

1. C:

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isMatch(char *s, char *p) {
    int m = strlen(s);
    int n = strlen(p);
    
    bool dp[m+1][n+1];
    memset(dp, false, sizeof(dp));
    
    dp[0][0] = true; // Both empty string and pattern match

    // Initialize the first row for patterns starting with '*'
    for (int j = 1; j <= n; j++) {
        if (p[j-1] == '*') {
            dp[0][j] = dp[0][j-1];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == s[i-1] || p[j-1] == '?') {
                dp[i][j] = dp[i-1][j-1]; // Exact match or '?'
            } else if (p[j-1] == '*') {
                dp[i][j] = dp[i-1][j] || dp[i][j-1]; // '*' matches one or more characters
            }
        }
    }

    return dp[m][n];
}

int main() {
    char s[] = "adceb";
    char p[] = "*a*b";
    printf("%d\n", isMatch(s, p)); // Output: 1 (true)
    return 0;
}

2. C++:

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

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    
    dp[0][0] = true;

    for (int j = 1; j <= n; j++) {
        if (p[j-1] == '*') {
            dp[0][j] = dp[0][j-1];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == s[i-1] || p[j-1] == '?') {
                dp[i][j] = dp[i-1][j-1];
            } else if (p[j-1] == '*') {
                dp[i][j] = dp[i-1][j] || dp[i][j-1];
            }
        }
    }

    return dp[m][n];
}

int main() {
    string s = "adceb", p = "*a*b";
    cout << isMatch(s, p) << endl; // Output: 1 (true)
    return 0;
}

3. Java:

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        
        dp[0][0] = true;

        for (int j = 1; j <= n; j++) {
            if (p.charAt(j-1) == '*') {
                dp[0][j] = dp[0][j-1];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '?') {
                    dp[i][j] = dp[i-1][j-1];
                } else if (p.charAt(j-1) == '*') {
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isMatch("adceb", "*a*b")); // Output: true
    }
}

4. Python:

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    dp[0][0] = True

    for j in range(1, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-1]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == s[i-1] or p[j-1] == '?':
                dp[i][j] = dp[i-1][j-1]
            elif p[j-1] == '*':
                dp[i][j] = dp[i-1][j] or dp[i][j-1]

    return dp[m][n]

# Example usage:
print(isMatch("adceb", "*a*b"))  # Output: True

5. C#:

public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        bool[,] dp = new bool[m + 1, n + 1];
        
        dp[0, 0] = true;

        for (int j = 1; j <= n; j++) {
            if (p[j-1] == '*') {
                dp[0, j] = dp[0, j-1];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j-1] == s[i-1] || p[j-1] == '?') {
                    dp[i, j] = dp[i-1, j-1];
                } else if (p[j-1] == '*') {
                    dp[i, j] = dp[i-1, j] || dp[i, j-1];
                }
            }
        }

        return dp[m, n];
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        Console.WriteLine(solution.IsMatch("adceb", "*a*b")); // Output: True
    }
}

6. JavaScript:

var isMatch = function(s, p) {
    const m = s.length, n = p.length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
    
    dp[0][0] = true;

    for (let j = 1; j <= n; j++) {
        if (p[j-1] === '*') {
            dp[0][j] = dp[0][j-1];
        }
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j-1] === s[i-1] || p[j-1] === '?') {
                dp[i][j] = dp[i-1][j-1];
            } else if (p[j-1] === '*') {
                dp[i][j] = dp[i-1][j] || dp[i][j-1];
            }
        }
    }

    return dp[m][n];
};

// Example usage
console.log(isMatch("adceb", "*a*b"));  // Output: true

Summary:

  • Time Complexity: O(m * n), where m is the length of string s and n is the length of pattern p.
  • Space Complexity: O(m * n), for storing the DP table.