Free Tries lessonsTries · Stage 1 · Prefix questions · Step 2

Search with wildcards

A dot matches any single letter; branch into every child the trie has at that position. About 12 minutes.

Two kinds of steps

At a normal letter, the search does exactly what the exact-word check did: follow the one matching child, or fail if it is missing. At a wildcard, written as a dot, there is no single child to follow.

A dot is like a blank tile in a word game: it can be any letter. So the search tries every child the current node has, and succeeds if any one of them leads to a full match.

Exact letter: one child to check, same as before.

Wildcard: try every existing child; one success is enough.

words = [cat, cot, dog], pattern = "c.t"

'c' is a normal letter: follow the one matching child.

Move 1 of 3

When it succeeds

The recursion reaches the end of the pattern with a node in hand. That node must be marked as an end for the match to count. A path existing isn't enough, just as in the very first step of this topic.

Example: the pattern "c.t" matches "cat" and "cot", but not "ct" or "cart".

End of pattern: check the end marker instead of assuming a match.

In code

if c == ".":
    for child in node.values():
        print(child)     # every branch

Quick check

words = ["cat", "cot"], pattern = "c.t". Does it match?

AYes
BNo

Show the answer

Yes. The wildcard in the middle can be 'a' (matching "cat") or 'o' (matching "cot"); either succeeds.

Your problem

Search with wildcards

words is a list of lowercase words. pattern has the same length as some word and may contain '.', which matches any single letter. Return true if pattern matches any word in words, or false otherwise.

Example

words = ["cat", "cot", "dog"], pattern = "c.t" → true

0 ≤ words.length ≤ 1,000 · 1 ≤ words[i].length, pattern.length ≤ 20 · every word and pattern character is lowercase a-z or '.'

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.