Find all the words in a list that are next to a given word | shanhe.me

Find all the words in a list that are next to a given word | shanhe.me

There is a list of four-letter words, such as aahs, aals, abas, abba, etc. Given an arbitrary four-letter word, find all the words in the list that are next to the given word, i.e., words that can be the same as the given word with exactly one letter changed. Example: given puma, the result could be duma, pima, puja, pula, pump, puna, pupa.

We use an index-based solution, and we give the result containing unique and sorted words from the list.

Suppose we look up words for puma, then we

1. find words from the list that have the pattern ?uma with ? less than p.
2. find words from the list that have the pattern p?ma with ? less than u.
3. find words from the list that have the pattern pu?a with ? less than m.
4. find words from the list that have the pattern pum? with ? less than a.
5. find words from the list that have the pattern pum? with ? greater than a.
6. find words from the list that have the pattern pu?a with ? greater than m.
7. find words from the list that have the pattern p?ma with ? greater than u.
8. find words from the list that have the pattern ?uma with ? greater than p.

and combine the results in the order of the steps to get the final result. Note that if the result from each step contains unique and sorted words, then the final list contains unique and sorted words.

The index for unique and sorted words from the list matching a pattern like ?uma with ? less than or greater than p can be designed like

Read full article from Find all the words in a list that are next to a given word | shanhe.me