each word s in the dictionary is mapped/hashed into multiple keys, where
each key is the word minus one letter, for example, if word is "cat"
then there are 4 entries with value "cat"
key="cat"
key="ca"
key="ct"
key="at"
Now two words have distance of 1 iff they have a common key.
Proof:
1. if two words w1 and w2 have distance of 1, then it is either an insert/
delete/change. All three will have w1 and w2 map into one common key.
2. if two words w1 and w2 have a common key, then that key is either the
word itself or the word remove one letter. It is easily verified that w1 and
w2 have distance at most 1.
Now each word w is mapped into at most |w| keys, where |w| is the number of
letters in w. Since English words are in general short, less than 15 letters
. We use space O(n * max|w|) and all words with distance at most 1 will be
in the same hash table entry. The value of each hashtable entry is a list of
words, and they all have distance at most 1 between each other.
