44. Wildcard Matching - Leetcode

Wildcard Matching

Difficulty: Hard

Problem Statement

Given an input string s and a pattern p, implement wildcard matching with support for the following:

  • '?' matches any single character.
  • '*' matches any sequence of characters (including an empty sequence).

The match should cover the entire input string, not just a partial match.

Examples

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence of characters.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but 'a' does not match 'b'.

Constraints

  • 0 <= s.length, p.length <= 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '?', or '*'.

Approach: Dynamic Programming (Bottom-Up)

To efficiently solve this problem, we use Dynamic Programming (DP).

Step 1: Define the DP Table

We create a 2D table dp[i][j], where:

  • dp[i][j] = true if the first i characters of s match the first j characters of p.

Why DP?

  • '*' can match multiple characters, requiring us to track results of smaller subproblems.
  • A table-based approach avoids redundant calculations.

Step 2: Base Cases

  1. Empty string matches an empty pattern:
    • dp[0][0] = true (Empty pattern matches an empty string).
  2. Handling patterns with leading '*':
    • If p[j-1] == '*', then dp[0][j] = dp[0][j-1] (i.e., '*' behaves as an empty match).

Step 3: Filling the DP Table

We iterate through s and p, applying these rules:

  1. Character Matches (s[i-1] == p[j-1] or p[j-1] == '?')
    • If characters match or p[j-1] == '?', then:
      dp[i][j] = dp[i-1][j-1];
      
  2. Handling '*' (Matches Any Sequence)
    • '*' can:
      • Match zero charactersdp[i][j] = dp[i][j-1]
      • Match one or more charactersdp[i][j] = dp[i-1][j]
    • Formula:
      dp[i][j] = dp[i-1][j] || dp[i][j-1];
      

C# Implementation

using System;

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];

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

        // Fill first row for patterns with '*'
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[0, j] = dp[0, j - 1];  // '*' matches empty sequence
            }
        }

        // Fill DP table
        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];  // Match single character or '?'
                } else if (p[j - 1] == '*') {
                    dp[i, j] = dp[i - 1, j] || dp[i, j - 1];  // '*' matches one or more OR empty
                }
            }
        }

        return dp[m, n];
    }
}

// Example Usage
class Program {
    static void Main() {
        Solution solution = new Solution();
        
        Console.WriteLine(solution.IsMatch("aa", "a"));       // false
        Console.WriteLine(solution.IsMatch("aa", "*"));       // true
        Console.WriteLine(solution.IsMatch("cb", "?a"));      // false
        Console.WriteLine(solution.IsMatch("adceb", "*a*b")); // true
        Console.WriteLine(solution.IsMatch("acdcb", "a*c?b"));// false
    }
}

Complexity Analysis

Approach Time Complexity Space Complexity
DP Table O(m × n) O(m × n)
Optimized DP (1D Array) O(m × n) O(n)

Optimized Approach (Space Reduction)

Instead of a 2D table, we can use two 1D arrays (current and previous row), reducing space from O(m × n) to O(n).


Example Walkthrough

Example 1: s = "aa", p = "a"

a
a T
a F

Output: false

Example 2: s = "aa", p = "*"

*
a T
a T

Output: true


Edge Cases Considered

✅ Empty s or p
✅ Pattern with multiple '*'
✅ Pattern with '?'
✅ No wildcards


Summary

DP Table efficiently stores subproblem results.
✅ Handles '*' and '?' effectively.
Optimized Space Approach reduces memory usage.

This C# solution ensures efficient wildcard pattern matching! 🚀

Featured Posts

3. Longest Substring Without Repeating Characters - Leetcode

Longest Substring Without Repeating Characters Difficulty: Medium Problem Statement: Given a string s , find the length of the longest ...

Popular Posts