Practice eBay Coding Question | Real Coding Interviews

Quick Summary

Find all words in a dictionary that completely match a pattern containing literals, '?', and '.'.
? matches exactly one character while '.' matches one or more consecutive characters.
A valid match requires consuming both the entire pattern and the entire word simultaneously.

What This Tests

String pattern matching logic
Dynamic programming state transitions
Handling variable-length wildcards
Multi-step state tracking

Common Patterns

Dynamic Programming

Two Pointers

(This question is a variation of the LeetCode question 44. Wildcard Matching. If you haven't completed that question yet, it is recommended to solve it first.)

Given a list of distinct words wordDict and a pattern string, return all words in wordDict that match the pattern. A pattern is matched from left to right using three rules:

A lowercase letter matches only the identical letter in the word.
'?' matches exactly one character.
'.' matches one or more consecutive characters. It must consume at least one character.

Test Cases

Input

Output

Expected