LC: Shortest Word Distance II - spiralgo/algorithms GitHub Wiki

Shortest Word Distance II

The Essence:

words array is provided to the class at initialization-time. So, a procedure can place all the indices a word has into a map. When a query is received, instead of looping through the entire words array, the program can only loop through the indices of the two words to compare.

With this, the problem demonstrates how some preprocessing can help solving query problems.

Details:

The indices of a words can be stored using a hash table. When comparing the words by their indices, it's helpful to use two pointers for keeping the index of the index array, because the array is sorted. A negative distance implies that the first index has to go up. A positive index implies that the second word's index needs to go up to catch up to the first's.