Katkat
Back

Match a string with wildcard pattern recursively

CitadelData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement a recursive pattern-matching algorithm that handles specific wildcard characters while managing overlapping subproblems.

Problem Statement

Implement a function is_match(text, pattern) that returns True if the pattern matches the entire text and False otherwise. The pattern supports two special wildcard characters:

  • ?: Matches any single character.
  • *: Matches any sequence of characters (including an empty sequence).

Function Signature

def is_match(text: str, pattern: str) -> bool:

Constraints

  • 0 <= len(text) <= 1000
  • 0 <= len(pattern) <= 1000
  • The string and pattern consist of lowercase English letters, ?, and *.

Examples

Example 1: Input: text = "aa", pattern = "*" Output: True Explanation: * matches the entire string "aa".

Example 2: Input: text = "cb", pattern = "?a" Output: False Explanation: ? matches 'c', but 'a' does not match 'b'.

Example 3: Input: text = "adceb", pattern = "*a*b" Output: True Explanation: The first * matches "d", the second * matches "ce".

Edge Cases

  • Empty text and empty pattern should return True.
  • Patterns with multiple consecutive * (e.g., **a) should be treated as a single *.

Hints

Hint 1

Consider the base cases: when the pattern is exhausted, return true if the text is also empty; when the text is exhausted, return true only if the remaining pattern is all '*' characters.

Hint 2

For the recursive step, if the characters match or the pattern has '?', proceed to the next index in both; if you encounter a '*', branch into two paths: skipping the '*' or using it to match one character.

Hint 3

Because the recursive approach has overlapping subproblems, consider using memoization to store results of `(text_index, pattern_index)` pairs to optimize performance to O(T*P).

Follow-up questions

  • How does the time and space complexity change if you transition from a recursive solution with memoization to an iterative dynamic programming table?
  • Can you optimize the space complexity of the iterative DP solution to O(P) using only two rows?
  • How would you modify your algorithm if the '*' wildcard was redefined to match only non-empty sequences of characters?