Shortest word distance I, II && III

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

For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = "makes", word2 = "coding", return 1.

Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

All three follows the similar approach. For the first one, we keep two pointers, each points to the last position of the desired word. If both of the pointers are valid, we calculate the distance and compare with the last one we got.

public int shortestDistanceI(String[] words, String word1, String word2) {
        int pos1 = -1, pos2 = -1, dist = Integer.MAX_VALUE;
        for(int i = 0; i < words.length; i++) {
            if (word1.equals(words[i])) {
                pos1 = i;
            }
            if (word2.equals(words[i])) {
                pos2 = i;
            }
            if (pos1 >= 0 && pos2 >= 0) {
                dist = Math.min(dist, Math.abs(pos1 - pos2));
            }
        }
        return dist;
    }

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = "makes", word2 = "coding", return 1.

Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

For the second one, now there will be multiple operations, the easiest would be using a hash map to store the position of the words, and every time the function is called, we calculate the minimum distance. We can also use a "cache" matrix to store the minimum distance if we already calculate once (not implemented).

public class ShortestWordDistanceII {
    Map<String, List<Integer>> map = new HashMap<>();

    public ShortestWordDistanceII(String[] words) {
        for (int i = 0; i < words.length; i++) {
            if (!map.containsKey(words[i])) {
                map.put(words[i], new ArrayList<>());
            }
            map.get(words[i]).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> first = map.get(word1);
        List<Integer> second = map.get(word2);
        int i = 0, j = 0, dist = Integer.MAX_VALUE;
        while (i < first.size() && j < second.size()) {
            int pos1 = first.get(i);
            int pos2 = second.get(j);
            dist = Math.min(dist, Math.abs(pos1 - pos2));
            if (pos1 < pos2) {
                i++;
            } else {
                j++;
            }
        }
        return dist;
    }
}

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

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

word1 and word2 may be the same and they represent two individual words in the list.

For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “makes”, word2 = “coding”, return 1. Given word1 = "makes", word2 = "makes", return 3.

Note: You may assume word1 and word2 are both in the list.

The third one follows exactly the same as the first one, the only difference is that if pointer 1 is the same of pointer 2, we pass it. Note we need to calculate distance every time we update one of the pointers.

public int shortestDistanceIII(String[] words, String word1, String word2) {
        int pos1 = -1, pos2 = -1, dist = Integer.MAX_VALUE;
        for(int i = 0; i < words.length; i++) {
            if (word1.equals(words[i])) {
                pos1 = i;
                if (pos1 >= 0 && pos2 >= 0) {
                    dist = pos1 != pos2 ? Math.min(dist, Math.abs(pos1 - pos2)) : dist;
                }
            }
            if (word2.equals(words[i])) {
                pos2 = i;
                if (pos1 >= 0 && pos2 >= 0) {
                    dist = pos1 != pos2 ? Math.min(dist, Math.abs(pos1 - pos2)) : dist;
                }
            }

        }
        return dist;
    }