This looks like a variant of the edit distance problem, but it is simpler. An "edit" here is only a substitution, not an insertion or deletion. Every string in queries and dictionary has the same length, so we never add or remove characters. We only need to check whether a query word can be transformed into some dictionary word by changing at most 2 characters.

Because the lengths match, "two edits" means "the two words differ in at most 2 positions." So for each query word, we compare it character-by-character with each dictionary word and count the positions where they differ. If any dictionary word differs in at most 2 positions, the query word qualifies.

The remaining question is whether we can do better than comparing every query against every dictionary word. A Trie lets us search all dictionary words at once while tracking a shared mismatch budget, which is the second approach below.

Key Constraints:

Intuition

For each query word, check it against every word in the dictionary. Since all words have the same length, two edits means the words differ in at most 2 positions. So we compare both words character by character, count mismatches, and stop as soon as the count passes 2.

With at most 100 queries, 100 dictionary words, and words up to 100 characters, that is at most 1,000,000 character comparisons. The early stop reduces this further whenever a pair diverges quickly.

Algorithm

Visualization and Code

This is fast enough for the given constraints. The next approach organizes the dictionary into a structure that searches all words at once and reuses shared prefixes.

Intuition

A Trie (prefix tree) stores all dictionary words in a tree where shared prefixes share a single path. We search for a query word by walking down the Trie character by character, allowing up to 2 mismatches along the way.

At each node, we try every child. If the child's character equals the query character at the current depth, we descend with the edit count unchanged. If it differs, we descend with the edit count incremented by 1. We explore every branch but abandon any path once its edit count exceeds 2. If a path reaches the end of a dictionary word with 2 or fewer edits, the query word qualifies.

This is a DFS with a mismatch budget. Because words that share a prefix share the same Trie path, that prefix is traversed once per query instead of once per dictionary word, which is the saving over brute force. The budget bounds the search: at most 2 levels can take a mismatching branch, so once edits reach 2 every remaining character must match exactly, and the DFS collapses to following a single fixed path.

Algorithm

Visualization and Code