**Word Distance I – Only called once**

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.

Solution: One pass. O(n), Every time find an occurrence of word1 or word2, compare the distance of p1 and p2.

public int shortestDistance(String[] words, String word1, String word2) { int p1 = -1, p2 = -1, min = Integer.MAX_VALUE; for (int i = 0; i < words.length; i++) { if (words[i].equals(word1)) p1 = i; if (words[i].equals(word2)) p2 = i; if (p1 != -1 && p2 != -1) min = Math.min(min, Math.abs(p1 - p2)); } return min; }

**Shortest Word Distance II – API, will be called multiple times**

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.

Solution: First preprocess the word to dict, which is a <word, list of index>map.

Then every time just get the word only check two list of indexes.

public class WordDistance { Map<String, List<Integer>> dict; public WordDistance(String[] words) { dict = new HashMap<>(); for(int i=0;i<words.length;i++){ if(dict.containsKey(words[i])){ dict.get(words[i]).add(i); }else{ List<Integer> indexes = new ArrayList<>(); indexes.add(i); dict.put(words[i], indexes); } } } public int shortest(String word1, String word2) { if(dict==null||!dict.containsKey(word1)||!dict.containsKey(word2)){ return 0; } int res = Integer.MAX_VALUE; List<Integer> indexes1 = dict.get(word1); List<Integer> indexes2 = dict.get(word2); int index1 = 0; int index2 = 0; while(index1<indexes1.size()&&index2<indexes2.size()){ res = Math.min(res, Math.abs(indexes1.get(index1)-indexes2.get(index2))); if(indexes1.get(index1)<indexes2.get(index2)){ index1++; }else{ index2++; } } return res; } }

**Shortest Word Distance III – word1 could be the same as word2**

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.

Solution: if word1==word2==words[], then p1=p2=i, and every time we update p1, we check the distance between p1 and p2.

public int shortestWordDistance(String[] words, String word1, String word2) { int p1 = -1, p2 = -1, min = Integer.MAX_VALUE; for (int i = 0; i < words.length; i++) { if (words[i].equals(word1)) { p1 = i; if (word1.equals(word2) && p1 != -1 && p2 != -1) { min = Math.min(min, Math.abs(p1 - p2)); } } if (words[i].equals(word2)) { p2 = i; } if (!word1.equals(word2) && p1 != -1 && p2 != -1) { min = Math.min(min, Math.abs(p1 - p2)); } } return min; }