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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Wildcard Matching

Number: 44

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Bloomberg, Meta, Microsoft, Zoho, Walmart Labs, TikTok, Adobe, Apple, Confluent, Salesforce, Coursera, Two Sigma, X, Snap

Problem Description

Given a string s and a pattern p, implement wildcard matching where:

  • '?' matches any single character.
  • '*' matches any sequence of characters (including the empty sequence). The matching must cover the entire string s.

Key Insights

  • Use dynamic programming to track matching status between prefixes of s and p.
  • When p[j] is a regular character or '?', check for character match (or any character match for '?').
  • When p[j] is '*', it can match an empty sequence (dp[i][j-1]) or extend a previous match (dp[i-1][j]).
  • A greedy two-pointer approach can also be considered, but the DP solution is clearer for handling worst-case scenarios.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of s and m is the length of p. Space Complexity: O(n * m), due to the DP table used to store matching results.

Solution

We solve the problem using a dynamic programming approach by constructing a boolean table dp, where dp[i][j] indicates whether the first i characters of s match the first j characters of p. The recurrence is as follows:

  • If p[j-1] is a normal character or '?', then dp[i][j] = dp[i-1][j-1] if the current characters match (or p[j-1] is '?').
  • If p[j-1] is '', then dp[i][j] is true if either the star matches no characters (dp[i][j-1]) or if it matches one more character (dp[i-1][j]). A careful initialization of the dp table is required, especially for patterns that start with '' which can match empty strings.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with line-by-line comments.

def isMatch(s: str, p: str) -> bool:
    n, m = len(s), len(p)
    # Create a DP table with (n+1) x (m+1) initialized to False
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    # Empty string matches empty pattern
    dp[0][0] = True

    # Initialize first row for patterns that have '*' which can match empty string
    for j in range(1, m + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]

    # Build 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]:
                # Characters match or pattern has '?' so inherit the previous state
                dp[i][j] = dp[i - 1][j - 1]
            elif p[j - 1] == '*':
                # '*' matches empty sequence: dp[i][j-1] or one/more characters: dp[i-1][j]
                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
            else:
                dp[i][j] = False

    return dp[n][m]

# Example usage:
print(isMatch("aa", "a"))   # False
print(isMatch("aa", "*"))   # True
print(isMatch("cb", "?a"))  # False
← Back to All Questions