Design a pattern matching system

Problem

Design and implement a pattern matching system that enables flexible string searching with wildcard support. Your system should handle two types of wildcard characters:

• * (asterisk): Matches zero or more of any characters
• ? (question mark): Matches exactly one character

The matcher should determine whether a given text string matches a pattern containing these wildcards.

Requirements

1. Implement a PatternMatcher class with a matches method
2. The matches method accepts two parameters: a pattern string and a text string
3. Return true if the text matches the pattern, false otherwise
4. Support the * wildcard to match any sequence of zero or more characters
5. Support the ? wildcard to match exactly one character
6. Handle patterns with multiple wildcards in various positions
7. Regular characters in the pattern must match exactly

Constraints

• 0 ≤ pattern length ≤ 1000
• 0 ≤ text length ≤ 1000
• Both strings contain only lowercase English letters and wildcard characters
• Time complexity should be reasonable for the given input sizes
• Pattern contains only lowercase letters, *, and ? characters

Examples

Example 1:

Pattern: "hello" Text: "hello" Output: true Explanation: Exact match with no wildcards

Example 2:

Pattern: "h?llo" Text: "hello" Output: true Explanation: The '?' matches 'e'

Example 3:

Pattern: "h*o" Text: "hello" Output: true Explanation: The '*' matches 'ell'

Example 4:

Pattern: "a*b" Text: "aXYZb" Output: true Explanation: The '*' matches 'XYZ'

Example 5:

Pattern: "a*b*c" Text: "abc" Output: true Explanation: Both '*' wildcards match empty strings

Hint 1: Dynamic Programming Approach Consider using dynamic programming where you build a 2D table tracking whether substrings match sub-patterns. Define dp[i][j] as whether the first i characters of the text match the first j characters of the pattern.

Hint 2: Handling Wildcards For the ? wildcard, you need to ensure there's a character to match and advance both pointers. For *, you have two choices: match zero characters (skip the *) or match one or more characters (consume a character from the text and keep the * active).

Hint 3: Base Cases Think about the base cases: an empty pattern matches only an empty text, but a pattern consisting only of * characters can match an empty text. How do you initialize your DP table to reflect these cases?

Full Solution `` Solution Explanation:

This solution uses dynamic programming to solve the pattern matching problem efficiently.

Approach:

1. DP Table Definition: Create a 2D boolean table dp[i][j] where dp[i][j] is True if the first i characters of the text match the first j characters of the pattern.

2. Base Cases:

   • dp[0][0] = True: An empty pattern matches an empty text
   • If the pattern starts with consecutive * characters, they can match an empty text since * can match zero characters

3. State Transitions:

   • Asterisk (*): Has two options:

     • Match zero characters: inherit the result from dp[i][j-1]
     • Match one or more characters: inherit from dp[i-1][j] (keep using the same *)

   • Question mark (?): Must match exactly one character, so inherit from dp[i-1][j-1]

   • Regular character: Must match exactly with the current text character, check if characters match AND inherit from dp[i-1][j-1]

4. Result: The answer is in dp[m][n] where m and n are the lengths of text and pattern respectively.

Complexity Analysis:

• Time Complexity: O(m × n) where m is the length of the text and n is the length of the pattern. We fill each cell of the DP table exactly once.
• Space Complexity: O(m × n) for storing the DP table. This can be optimized to O(n) by using only two rows since we only need the previous row to compute the current row.

Alternative Approach:

A recursive solution with memoization is also possible, which can be more intuitive but has similar time and space complexity.

class PatternMatcher:
    def __init__(self):
        pass
    
    def matches(self, pattern: str, text: str) -> bool:
        """
        Determines if the text matches the given pattern using dynamic programming.
        
        Time Complexity: O(m * n) where m is text length, n is pattern length
        Space Complexity: O(m * n) for the DP table
        """
        m, n = len(text), len(pattern)
        
        # dp[i][j] represents whether text[0:i] matches pattern[0:j]
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        
        # Base case: empty pattern matches empty text
        dp[0][0] = True
        
        # Handle patterns starting with '*' which can match empty text
        for j in range(1, n + 1):
            if pattern[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):
                pattern_char = pattern[j - 1]
                text_char = text[i - 1]
                
                if pattern_char == '*':
                    # '*' can match zero characters or one or more characters
                    # dp[i][j-1]: skip the '*', match zero characters
                    # dp[i-1][j]: use the '*' to match current text character
                    dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
                elif pattern_char == '?':
                    # '?' matches exactly one character
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    # Regular character must match exactly
                    dp[i][j] = dp[i - 1][j - 1] and pattern_char == text_char
        
        return dp[m][n]