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

Problem Statement: Wildcard Matching

Given two strings s and p, return true if s matches p (with wildcard characters), and false otherwise.

The string p can contain the following wildcard characters:

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

Example:

Example 1:

Input: s = "aa", p = "a*"
Output: true
Explanation: "a*" matches "aa" because '*' can match the second 'a'.

Example 2:

Input: s = "mississippi", p = "mis*is*p*."
Output: false

Example 3:

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

---

Approach:

The problem can be solved using Dynamic Programming (DP). The idea is to use a 2D DP table where dp[i][j] represents whether the substring s[0..i-1] matches the pattern p[0..j-1].

Steps:

1. Base Case:
   • dp[0][0] = true: An empty string matches an empty pattern.
   • dp[i][0] = false for i > 0: A non-empty string cannot match an empty pattern.
   • dp[0][j] = true for all j where the pattern consists only of *. This is because * can match any sequence of characters, including the empty string.
2. Filling the DP Table:
   • For each character in the string s and the pattern p:
     • If p[j-1] == s[i-1] or p[j-1] == '?', then dp[i][j] = dp[i-1][j-1], meaning the current character in s matches the current character in p.
     • If p[j-1] == '*', then we have two possibilities:
       • dp[i][j] = dp[i-1][j]: The * matches at least one character in s.
       • dp[i][j] = dp[i][j-1]: The * matches zero characters in s.
3. Final Result:
   • The value of dp[len(s)][len(p)] will give the result of whether the entire string s matches the pattern p.

---

Dynamic Programming Solution:

Python Code:

def isMatch(s: str, p: str) -> bool:
    # dp[i][j] will be True if s[0...i-1] matches p[0...j-1]
    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
    
    # Initial condition: empty string matches empty pattern
    dp[0][0] = True
    
    # If the pattern starts with '*' it can match the empty string
    for j in range(1, len(p) + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]
    
    # Fill the dp table
    for i in range(1, len(s) + 1):
        for j in range(1, len(p) + 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]
    
    # The bottom-right corner will contain the answer
    return dp[len(s)][len(p)]

---

Explanation of the Code:

1. Initialization:
   • We initialize a 2D DP table dp of size (len(s) + 1) x (len(p) + 1), where each cell dp[i][j] will store whether the substring s[0..i-1] matches the pattern p[0..j-1].
   • dp[0][0] = True because an empty string matches an empty pattern.
   • For the first row (dp[0][j]), if the pattern starts with *, it can match the empty string, so we set dp[0][j] to True for any * characters in the pattern.
2. Filling the DP Table:
   • We iterate through each character in s and p and apply the rules:
     • If the current character in the pattern is ?, it matches any single character in s.
     • If the current character in the pattern is *, it can either match zero or more characters in s. Thus, we check:
       • If * matches zero characters, check the cell to the left (dp[i][j-1]).
       • If * matches at least one character, check the cell above (dp[i-1][j]).
3. Final Answer:
   • After filling the DP table, dp[len(s)][len(p)] will contain the final answer: whether the entire string s matches the entire pattern p.

---

Time and Space Complexity:

• Time Complexity: O(m * n), where m is the length of s and n is the length of p. We need to fill an m x n DP table.
• Space Complexity: O(m * n), as we are storing the DP table of size m x n.

---

Example Walkthrough:

Example 1:

Input: s = "aa", p = "a*"

• Initialize dp table.
• First Row (dp[0][j]): For p = "a*", dp[0][2] = True, as * can match the empty string.
• Second Row (dp[1][j]): For s = "a", the pattern a* matches:
  • dp[1][1] = True because p[0] == s[0].
  • dp[1][2] = True because * can match the second a.
• Third Row (dp[2][j]): For s = "aa", the pattern a* matches:
  • dp[2][1] = False (no match).
  • dp[2][2] = True because * matches the second a.

The final result is True, as dp[2][2] = True.

Example 2:

Input: s = "mississippi", p = "mis*is*p*."

• After filling the DP table, the value dp[len(s)][len(p)] will be False, because the pattern mis*is*p*. does not match the string "mississippi".

---

Conclusion:

The Wildcard Matching problem is efficiently solved using Dynamic Programming. By filling a DP table and considering all possible ways a wildcard can match a sequence of characters, we can determine if the string matches the pattern with wildcards * and ?. The time complexity of O(m * n) is suitable for handling reasonably large inputs, where m and n are the lengths of the string and the pattern, respectively.