Words Within Two Edits of Dictionary

Words Within Two Edits of Dictionary

What is this problem about?

You are given a list of queries and a dictionary of words (all words have the same length). For each query, you need to check if there is any word in the dictionary that can be transformed into the query word with at most two edits. An edit is defined as changing one character at a specific position.

Why is this asked in interviews?

This problem evaluates your understanding of String Comparison and potential optimizations for "fuzzy" matching. While it can be solved with a simple nested loop for small inputs, interviewers at Meta and Google might ask how to scale this or use a Trie to prune the search space.

Algorithmic pattern used

The simplest pattern is a Brute Force with Early Exit. Since you only allow two edits, for each query, you iterate through the dictionary and count the number of mismatches. If you find a word with <= 2 mismatches, you stop and add the query to your result. For larger datasets, a Trie-based DFS with a "remaining edits" counter can be used to skip branches that already have more than two differences.

Example explanation

Dictionary: ["apple", "banana"], Query: ["apply", "appel"].

1. apply vs apple: Differences at index 4 ('y' vs 'e'). 1 edit. Valid!
2. appel vs apple: Differences at index 3 ('e' vs 'l') and index 4 ('l' vs 'e'). 2 edits. Valid! Result: ["apply", "appel"].

Common mistakes candidates make

• Confusing Edit Distance: Thinking this is Levenshtein distance (which includes insertions/deletions). Here, words are same length, so it's just Hamming distance.
• No Early Exit: Counting all mismatches even after you've already found 3 differences.
• Redundant Processing: Not realizing that once a query matches any dictionary word, you can stop checking that query.

Interview preparation tip

Always clarify the definition of "edit." If the words are same length and only substitutions are allowed, the problem is much simpler than a general edit distance problem.