Smart Matching

Problem statement

Given a list of different words and an array of string queries, return a boolean array answer where answer[i] is true if you can change exactly one character in the $i^{th}$ query string to match any word in the list; return false otherwise.

Example

Sample input

Sample output

Explanation

"able" cannot be converted to any word in the list by modifying just one character.
"bat" can be converted to "cat" by changing "b" to "c".
"cap" can be converted to "cat" by changing "p" to "t".

Try it yourself

Try to solve the problem yourself before reading the solution.

Intuition

Let's modify the problem to a simpler version first. Suppose a list of words and a string is given to us and we're asked to find if the given string exists in the dictionary or not. In this case, we can insert all the dictionary words into a trie, iterate through all the letters in the strings, and search for the query word in the trie. The above problem requires us to solve something similar, with the added condition that one letter of the word might not match.

Let's take the example where the word cat is present in the list. As per the given conditions, if a user is trying to find any of aat, bat, dat, eat, fat, etc., the output should be true in all these cases because these words differ in only a letter from the original word cat.

This provides an intuition that we can insert all the possible one-letter-away words into the trie and then search for the given query word. However, this way, we insert many more words in the trie, consuming much more memory. Alternatively, we can replace each character of the word with a unique special character and then search for the query word. We modify the input query word by replacing each character with a special character and searching for it in the trie. For a word of length $W$, we would generate $W$ new words, but this is much less than replacing each character with all possible letters of the English alphabet.

For example, when searching for the word fat in the dictionary, we replace the first letter f with a special character _ and insert at in the trie. Similarly, we insert f_t and fa.

Now if we need to search for any one-character-away word from bat , we can convert bat into ba_, b_t, _at. We'll find a match for the string _at, denoting a word in the list that is just one character away from the word bat.

Algorithm

The summary of the algorithm is given below.

Step 1: Insertion in the trie

Generate a list of words where a special character, _, replaces each character of the word. Insert all these words in the trie. Please include an extra pointer in the trie node's children array to handle the special character.

Step 2: Searching in the trie

For each query word, generate all possible one-letter-away words, as in the step above, by replacing each character with _ one by one and creating a new word for each character replacement. Then, search ...