[LinkedIn] Shortest Word Distance

Problem: Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

Example:

Input: words = ["practice","makes","perfect","coding","makes"], word1 = "coding", word2 = "practice"
Output: 3
Explanation: IndexOf("coding") - IndexOf("practice") = 3 - 0 = 3

Input: words = ["practice","makes","perfect","coding","makes"], word1 = "makes", word2 = "coding"
Output: 1
Explanation: There are two places where "makes" is present in the array which is 1 and 4. The index of "coding" is 3 so the differences are 3 - 1 = 2 and 4 - 3 = 1. The minimum of theses distances (2, 1) is 1.

Constraints:

• word1 is not equal to word2
• word1 and word2 both are present in the given words array.

Approach: It's a straight forward problem to solve. You can look at the implementation to understand the approach.

Implementation in Java:

    public int shortestDistance(String[] words, String word1, String word2) 

    {

        int indexOfWord1 = -1;

        int indexOfWord2 = -1;

        int minDistance = Integer.MAX_VALUE;

        for (int i = 0; i < words.length; ++i) {

            if (words[i].equals(word1))

            {

                indexOfWord1 = i;

                if (indexOfWord2 != -1) {

                    minDistance = Math.min(minDistance, Math.abs(indexOfWord2 - indexOfWord1));

                }

            }

            if (words[i].equals(word2)) {

                indexOfWord2 = i;

                if (indexOfWord1 != -1) {

                    minDistance = Math.min(minDistance, Math.abs(indexOfWord2 - indexOfWord1));

                }

            }

        }

        return minDistance;

    }

Complexity: O(n)