# 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;`
12. `  }`
13. ` `
14. `  private static final Index[][][][] INDEX = new Index[][][];`
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.