DSA problem
Words Within Two Edits of Dictionary
You are given two string arrays queries and dictionary. All words in each array consist of the same length n. Return a list of all words from queries that can be transformed into some word from dictionary by changing at most two characters in total. A "change" replaces a single character at one position with any other character; positions can be changed independently as long as the total number of differing positions is at most two.
Since every query and every dictionary word has the same length n, "edits" here means Hamming distance, not full Levenshtein distance — we count differing positions, not insertions or deletions. That simplification is key because it means we never have to align strings, only compare them character by character.
A brute-force approach compares every query against every dictionary word, costing O(|queries| * |dictionary| * n). With each array containing up to 100 entries and n up to 100, that is feasible but wasteful: dictionary words sharing prefixes are compared from scratch every time.
A trie collapses the shared work. Insert every dictionary word into a 26-child trie. For each query, run a DFS through the trie that tracks the current depth (position in the query) and the running mismatch count. At each level, descend into the child equal to the query's current character (no extra mismatch) and into every other non-null child (one extra mismatch), as long as the total mismatch count stays <= 2. When the DFS reaches the bottom of any path with mismatch <= 2, the query qualifies. The pruning keeps this efficient: branches with mismatch > 2 are pruned immediately, so the average work per query is far less than the brute-force bound.
Examples
queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]["word","note","wood"]queries = ["yes"], dictionary = ["not"][]queries = ["abc","xyz"], dictionary = ["abd","xya"]["abc","xyz"]Constraints
- 1 <= queries.length, dictionary.length <= 100
- n == queries[i].length == dictionary[j].length
- 1 <= n <= 100
- All queries[i] and dictionary[j] consist of only lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.