Find all the words in a list that are next to a given word

Find all the words in a list that are next to a given word

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

  1. public final class WordIndex {
  2.  
  3.   private static class Entry {
  4.  
  5.     public String[] before;
  6.     public String[] after;
  7.   }
  8.  
  9.   private static class Index {
  10.  
  11.     public Entry[] entries = new Entry[26];
  12.   }
  13.  
  14.   private static final Index[][][][] INDEX = new Index[4][][][];
  15. }

The first dimension of INDEX denotes which letter we are changing, the second to fourth dimensions are for the fixed three letters. The class Index is for the changing letter. We first traverse all the words in the list, and mark the corresponding Entry as non-null in entries to get all the possibilities of the changing letter. Then we go back to each Index and build the full. The java implementation could have no import at all.

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.

More information about formatting options

To prevent automated spam submissions leave this field empty.