Wildcard Dictionary Matching
Company: eBay
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Wildcard Dictionary Matching
You are given a list of words (a dictionary) and a single search **pattern**. Return every word in the dictionary that the pattern matches, preserving the order in which the words appear in the dictionary.
The pattern is a string made up of three kinds of tokens:
- A **lowercase letter** (`a`–`z`) matches exactly that same letter.
- A **question mark** `?` matches **exactly one** character (any character).
- A **dot** `.` matches **one or more** characters (a contiguous run of length at least 1, any characters).
A word matches the pattern only if the **entire** word can be consumed by the **entire** pattern (full match, not a substring/prefix match). Tokens are matched left to right; a `.` may expand to cover as many characters as needed for the whole pattern to line up.
## Input
- `dictionary`: a list of strings. Each word consists of lowercase English letters and has length at least 1.
- `pattern`: a string consisting of lowercase English letters, `?`, and `.`.
## Output
- A list of the words from `dictionary` that match `pattern`, in their original dictionary order. Duplicate words in the dictionary should appear once per occurrence (do not deduplicate; just keep the words that match).
## Examples
Example 1
```
dictionary = ["cat", "cot", "cut", "coat", "ct"]
pattern = "c?t"
output = ["cat", "cot", "cut"]
```
`?` must match exactly one character, so `"coat"` (two characters between `c` and `t`) and `"ct"` (zero characters) do not match.
Example 2
```
dictionary = ["cat", "coat", "cart", "ct", "comment", "dog"]
pattern = "c.t"
output = ["cat", "coat", "cart", "comment"]
```
`.` matches one or more characters, so `"ct"` does not match (nothing between `c` and `t`), but `"cat"`, `"coat"`, `"cart"`, and `"comment"` all do. `"dog"` fails on the leading `c`.
Example 3
```
dictionary = ["a", "ab", "abc", "b"]
pattern = "a."
output = ["ab", "abc"]
```
`"a"` fails because `.` requires at least one trailing character; `"b"` fails the leading `a`.
Example 4
```
dictionary = ["hello", "help", "heap"]
pattern = "he?p"
output = ["help", "heap"]
```
`"hello"` has the wrong length and trailing letters, so it fails. `"help"` matches with `?` standing in for `'l'`, and `"heap"` also matches with `?` standing in for `'a'` — both are 4-character words of the form `h`, `e`, *(any one char)*, `p`.
## Constraints
- `1 <= len(dictionary) <= 10^4`
- `1 <= length of each word <= 100`
- `1 <= length of pattern <= 100`
- The dictionary words contain only lowercase English letters.
- The pattern contains only lowercase English letters, `?`, and `.`.
Report the total time complexity of your approach in terms of the number of words `n`, the maximum word length `m`, and the pattern length `p`, and briefly explain how you handle the `.` token (which can match a variable-length run).
Quick Answer: This question evaluates a candidate's ability to design custom pattern-matching logic beyond simple substring or regex lookups, handling both fixed-length and variable-length wildcard tokens. It tests string processing skills, dynamic programming or backtracking technique, and time-complexity analysis across a dictionary of words. Such questions are common in coding interviews to assess algorithmic problem-solving and precise handling of edge cases in string matching.
You are given a list of words (a `dictionary`) and a single search `pattern`. Return every word in the dictionary that the pattern matches, preserving the original dictionary order (do not deduplicate — keep every matching occurrence).
The pattern is made of three kinds of tokens:
- A **lowercase letter** (`a`-`z`) matches exactly that same letter.
- A **question mark** `?` matches **exactly one** character (any character).
- A **dot** `.` matches **one or more** characters (a contiguous run of length at least 1, any characters) — think of it as regex `.+`.
A word matches only if the **entire** word is consumed by the **entire** pattern (full match, not prefix/substring). Tokens are matched left to right; a `.` may expand to cover as many characters as needed for the whole pattern to line up.
**Example 1**
```
dictionary = ["cat", "cot", "cut", "coat", "ct"]
pattern = "c?t"
output = ["cat", "cot", "cut"]
```
`?` matches exactly one character, so `"coat"` (two chars between c and t) and `"ct"` (zero chars) do not match.
**Example 2**
```
dictionary = ["cat", "coat", "cart", "ct", "comment", "dog"]
pattern = "c.t"
output = ["cat", "coat", "cart", "comment"]
```
`.` matches one or more characters, so `"ct"` fails (nothing between c and t) while the rest match; `"dog"` fails on the leading `c`.
**Example 3**
```
dictionary = ["a", "ab", "abc", "b"]
pattern = "a."
output = ["ab", "abc"]
```
`"a"` fails because `.` requires at least one trailing character.
Return the matching words in dictionary order.
Constraints
- 1 <= len(dictionary) <= 10^4
- 1 <= length of each word <= 100
- 1 <= length of pattern <= 100
- Each dictionary word contains only lowercase English letters.
- The pattern contains only lowercase English letters, '?', and '.'.
- '?' matches exactly one character; '.' matches one or more characters.
- Full-word match required (not prefix or substring); output preserves dictionary order and does not deduplicate.
Examples
Input: (["cat", "cot", "cut", "coat", "ct"], "c?t")
Expected Output: ["cat", "cot", "cut"]
Explanation: '?' matches exactly one character, so 'coat' (two middle chars) and 'ct' (zero middle chars) are excluded.
Input: (["cat", "coat", "cart", "ct", "comment", "dog"], "c.t")
Expected Output: ["cat", "coat", "cart", "comment"]
Explanation: '.' matches one or more chars: 'ct' fails (no chars between c and t), 'dog' fails the leading 'c', the rest match with the dot covering runs of length 1-5.
Input: (["a", "ab", "abc", "b"], "a.")
Expected Output: ["ab", "abc"]
Explanation: 'a' fails because '.' needs at least one trailing char; 'b' fails the leading 'a'.
Input: (["hello", "help", "heap"], "he?p")
Expected Output: ["help", "heap"]
Explanation: 'hello' has the wrong length; 'help' and 'heap' are 4-char words of the form h,e,(any),p.
Input: ([], "a?")
Expected Output: []
Explanation: Empty dictionary yields an empty result.
Input: (["abc", "abc", "abd"], "abc")
Expected Output: ["abc", "abc"]
Explanation: A pure literal pattern matches only exact copies; duplicate matching words are kept (no deduplication).
Input: (["a", "aa", "ba"], "?")
Expected Output: ["a"]
Explanation: A single '?' matches exactly one character, so only the length-1 word 'a' qualifies.
Input: (["abcde", "axye", "ae", "abe"], "a.e")
Expected Output: ["abcde", "axye", "abe"]
Explanation: '.' expands to cover a variable-length middle run (3, 2, and 1 chars); 'ae' fails because the dot cannot match zero characters.
Hints
- Match each word independently, then filter the dictionary, preserving order. Focus on writing a correct full-match check for a single (word, pattern) pair.
- Use a boolean DP dp[i][j] meaning 'the first i characters of the word are fully consumed by the first j pattern tokens'. Base case dp[0][0] = True.
- For a literal letter, dp[i][j] = dp[i-1][j-1] and word[i-1] == token. For '?', dp[i][j] = dp[i-1][j-1] (exactly one char).
- For '.' (one or more), think of it as regex '.+': dp[i][j] = dp[i-1][j] (extend the current run to include word[i-1]) OR dp[i-1][j-1] (this is the first character of the run). Both require i >= 1, which is what forces the run to be non-empty.