Shortest Word Distance

Easy

Given a list of words and two wordsword1_and_word2, return the shortest distance between these two words in the list.

Example: Assume that words =["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “coding”, word2 = “practice”
Output: 3

Input: word1 = "makes", word2 = "coding"
Output: 1

Note: You may assume that word1 does not equal to word2, and _word1 _and _word2 _are both in the list.

Solution

One pass - O(n) time, O(1) space

We can greatly improve on the brute-force approach by keeping two indices i1 and i2 where we store the most recent locations of word1 and word2. Each time we find a new occurrence of one of the words, we do not need to search the entire array for the other word, since we already have the index of its most recent occurrence.

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int i1 = -1;
        int i2 = -1;
        int shortest = Integer.MAX_VALUE;

        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                i1 = i;
            }
            if (words[i].equals(word2)) {
                i2 = i;
            }

            if (i1 != -1 && i2 != -1) {
                shortest = Math.min(Math.abs(i1 - i2), shortest);
            }
        }
        return shortest;
    }
}

Reference

https://leetcode.com/problems/shortest-word-distance/solution/