We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Wildcard Matching

Difficulty: Hard

Problem Description

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

  • '?' matches any single character.
  • '*' matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial).

Key Insights

  • The '?' wildcard can replace any single character, making it versatile for matching.
  • The '*' wildcard can match zero or more characters, introducing complexity in handling multiple possibilities.
  • The problem can be solved using dynamic programming to efficiently manage overlapping subproblems.
  • The solution needs to ensure that both the pattern and the input string are fully utilized and matched.

Space and Time Complexity

Time Complexity: O(m * n), where m is the length of the pattern and n is the length of the string.
Space Complexity: O(m * n) for the DP table, but can be optimized to O(n) if using a single array for the previous row.

Solution

The solution employs a dynamic programming approach to create a 2D table where each entry dp[i][j] represents whether the first i characters of the string match the first j characters of the pattern. The algorithm iteratively fills this table by considering the cases for '?' and '*' and their respective matches.

  1. Initialize a DP table of size (m+1) x (n+1), where m is the length of the pattern and n is the length of the string.
  2. Set dp[0][0] to true since an empty pattern matches an empty string.
  3. Handle patterns that start with '*' by initializing the first row of the DP table.
  4. Iterate through the characters of the string and pattern to fill the DP table based on the matching rules.
  5. The final result will be found in dp[m][n].

Code Solutions

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    # Create a DP table with (m+1) x (n+1)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True  # Empty pattern matches empty string
    
    # Handle patterns that start with '*'
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]
    
    # Fill the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
            elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    
    return dp[m][n]
← Back to All Questions