Katkat
Back

Wildcard Dictionary Matching

eBaySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement a pattern-matching algorithm that supports variable-length wildcards using recursion with memoization or dynamic programming.

Problem Statement

You are given a dictionary of valid words and a search pattern. The pattern may contain two types of wildcards:

  1. ?: Matches exactly one character.
  2. *: Matches any sequence of characters (including an empty sequence).

Implement a function find_matches(dictionary, pattern) that returns a list of all words from the dictionary that match the given pattern.

Function Signature

def find_matches(dictionary: List[str], pattern: str) -> List[str]:

Constraints

  • 1 <= dictionary length <= 10,000
  • 1 <= word length <= 100
  • 1 <= pattern length <= 100
  • The pattern and dictionary words consist of lowercase English letters and the wildcard characters ? and *.

Examples

Example 1:

  • Input: dictionary = ["cat", "bat", "rat", "dog"], pattern = "?at"
  • Output: ["cat", "bat", "rat"]

Example 2:

  • Input: dictionary = ["apple", "apply", "ape", "april"], pattern = "ap*e"
  • Output: ["apple", "ape"]

Edge Cases

  • Empty dictionary or empty pattern.
  • Patterns containing only *.
  • No words matching the pattern.
  • Words that are shorter or longer than the effective pattern length.

Hints

Hint 1

Consider the `*` wildcard as a recursive choice: it can match zero characters (skip the `*`) or one character (consume one character from the word and stay at the `*`).

Hint 2

For each word in the dictionary, you can use a helper function `is_match(word, pattern)` that uses dynamic programming or memoized recursion to determine if the word satisfies the pattern.

Hint 3

A 2D memoization table `memo[i][j]` representing the match status of `word[i:]` and `pattern[j:]` can efficiently handle the subproblems.

Follow-up questions

  • How would you optimize this if you had to perform thousands of queries against the same fixed dictionary?
  • If the dictionary is massive (e.g., millions of words), what data structure would you use to store the dictionary to improve lookup speed?
  • How would you modify your solution to support a third wildcard character, like `[a-z]` bracket notation for character sets?