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

Shortest Word Distance III

The Essence:

If one of the two words occurred in some previous index p, and one of the two words occurred after this at q (without any middle occurrence), then the distance is a valid distance between these two words only if:

• They are the same word

OR

• words[p] != words[q]

Thus, it is enough to keep track of the last occurrence of either of the two words and compare it with the running minimum distance only if it satisfies the two conditions. Note that the indices p and q are not word-specific.

Details:

For the implementation of this logic, the procedure needs to keep track of the global minimum too. The sameness of the two strings can be checked at the beginning.