This is a follow up of . 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:

Use HashMap to store the indexs of each word.

1 public class WordDistance { 2     Map
     
      > wordMap; 3  4     public WordDistance(String[] words) { 5         wordMap = new HashMap
      
       >(); 6         for (int i = 0; i < words.length; i++) { 7             String word = words[i]; 8             if (wordMap.containsKey(word)) { 9                 wordMap.get(word).add(i);10             } else {11                 List
       
         list = new ArrayList
        
         ();12                 list.add(i);13                 wordMap.put(word, list);14             }15         }16     }17 18     public int shortest(String word1, String word2) {19         // Get two index lists20         List
         
           indList1 = wordMap.get(word1);21         List
          
            indList2 = wordMap.get(word2);22 int p1 = 0, p2 = 0;23 int minDis = Integer.MAX_VALUE;24 while (true) {25 if (indList1.get(p1) < indList2.get(p2)) {26 // Move p1.27 while (p1 < indList1.size() && indList1.get(p1) < indList2.get(p2)) {28 minDis = Math.min(minDis, Math.abs(indList1.get(p1) - indList2.get(p2)));29 p1++;30 }31 if (p1 >= indList1.size())32 break;33 } else {34 // Move p2.35 while (p2 < indList2.size() && indList2.get(p2) < indList1.get(p1)) {36 minDis = Math.min(minDis, Math.abs(indList1.get(p1) - indList2.get(p2)));37 p2++;38 }39 if (p2 >= indList2.size())40 break;41 }42 }43 return minDis;44 }45 }46 47 48 // Your WordDistance object will be instantiated and called as such:49 // WordDistance wordDistance = new WordDistance(words);50 // wordDistance.shortest("word1", "word2");51 // wordDistance.shortest("anotherWord1", "anotherWord2");