StringProblem 39 of 43

String matching where one string contains wildcard characters

Brute Force
Time: O(n * m * 2^m)
Space: O(n + m)
Optimal
Time: O(n * m)
Space: O(n * m)

Problem Statement

Given a text string and a wildcard pattern, implement wildcard pattern matching with support for ? and *.

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

The matching should cover the entire text string (not partial).

Example:

  • Input: text = "aab", pattern = "cab"
  • Output: false

Example 2:

  • Input: text = "adceb", pattern = "a*c?b"
  • Output: true (a*c matches "adc", ? matches "e", b matches "b")

Approach 1: Brute Force (Recursion)

Intuition

For each character in the pattern:

  • If it's a regular character, it must match the text character
  • If it's ?, it matches any single character
  • If it's *, try matching with 0, 1, 2, ... characters from text

Algorithm

  1. Base case: Both strings exhausted → true
  2. Base case: Pattern exhausted but text remains → false
  3. Base case: Text exhausted but pattern has only * → check remaining pattern
  4. If current pattern char is *, try matching:
    • 0 characters (move pattern pointer)
    • 1+ characters (move text pointer)
  5. If ? or matching char, advance both pointers
java
public class Solution {
    public boolean isMatch(String text, String pattern) {
        return match(text, pattern, 0, 0);
    }
    
    private boolean match(String text, String pattern, int t, int p) {
        if (p == pattern.length()) {
            return t == text.length();
        }
        
        if (t == text.length()) {
            for (int i = p; i < pattern.length(); i++) {
                if (pattern.charAt(i) != '*') return false;
            }
            return true;
        }
        
        char pChar = pattern.charAt(p);
        
        if (pChar == '*') {
            return match(text, pattern, t, p + 1) || 
                   match(text, pattern, t + 1, p);
        }
        
        if (pChar == '?' || pChar == text.charAt(t)) {
            return match(text, pattern, t + 1, p + 1);
        }
        
        return false;
    }
}

Complexity Analysis

  • Time Complexity: O(2^(n+m)) - Exponential due to * branching
  • Space Complexity: O(n + m) - Recursion stack

Approach 2: Memoization (Top-Down DP)

Intuition

The recursive solution has overlapping subproblems. Cache results to avoid recomputation.

java
import java.util.*;

public class Solution {
    private int[][] memo;
    
    public boolean isMatch(String text, String pattern) {
        int n = text.length(), m = pattern.length();
        memo = new int[n + 1][m + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        return match(text, pattern, 0, 0);
    }
    
    private boolean match(String text, String pattern, int t, int p) {
        if (p == pattern.length()) {
            return t == text.length();
        }
        
        if (t == text.length()) {
            for (int i = p; i < pattern.length(); i++) {
                if (pattern.charAt(i) != '*') return false;
            }
            return true;
        }
        
        if (memo[t][p] != -1) {
            return memo[t][p] == 1;
        }
        
        boolean result;
        char pChar = pattern.charAt(p);
        
        if (pChar == '*') {
            result = match(text, pattern, t, p + 1) || 
                     match(text, pattern, t + 1, p);
        } else if (pChar == '?' || pChar == text.charAt(t)) {
            result = match(text, pattern, t + 1, p + 1);
        } else {
            result = false;
        }
        
        memo[t][p] = result ? 1 : 0;
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n * m)
  • Space Complexity: O(n * m)

Approach 3: Tabulation (Bottom-Up DP) - Optimal

Intuition

Build solution bottom-up. dp[i][j] = true if text[0..i-1] matches pattern[0..j-1].

Algorithm

  1. Initialize dp[0][0] = true (empty matches empty)
  2. Handle patterns starting with * (can match empty text)
  3. Fill DP table based on recurrence relations
  4. Return dp[n][m]
java
public class Solution {
    public boolean isMatch(String text, String pattern) {
        int n = text.length(), m = pattern.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        
        dp[0][0] = true;
        
        for (int j = 1; j <= m; j++) {
            if (pattern.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char pChar = pattern.charAt(j - 1);
                char tChar = text.charAt(i - 1);
                
                if (pChar == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (pChar == '?' || pChar == tChar) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        
        return dp[n][m];
    }
}

Dry Run Example

text = "adceb", pattern = "a*c?b" DP Table: "" a * c ? b "" T F F F F F a F T T F F F d F F T F F F c F F T T F F e F F T F T F b F F T F F T Return dp[5][5] = True

Complexity Analysis

  • Time Complexity: O(n * m)
  • Space Complexity: O(n * m), can be optimized to O(m)

Approach 4: Space Optimized DP

Key Takeaways

  1. Two wildcards: ? matches exactly one, * matches zero or more
  2. DP is optimal - avoid exponential recursion
  3. Space optimization possible from O(n*m) to O(m)
  4. The * case: either match empty (move pattern) or match one char (move text)
  5. This is LeetCode 44 - a classic DP problem
  6. Related: Regular Expression Matching (with . and *)
Previous
Recursively remove all adjacent duplicates
Next
Function to find Number of customers who could not get a computer