244. Shortest Word Distance II

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

• WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict.
• int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

Example 1:

Input:
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]

Output:
[null, 3, 1]

Explanation:
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // returns 3
wordDistance.shortest("makes", "coding"); // returns 1

Constraints:
1 <= wordsDict.length <= 30,000
1 <= wordsDict[i].length <= 10
wordsDict[i] consists of lowercase English letters.
word1 and word2 are in wordsDict.
word1 != word2
At most 5,000 calls will be made to shortest

               public class WordDistance {
               
                   private Map> map;
                   
                   // Constructor initializes the map with the indices of each word
                   public WordDistance(String[] words) {
                       map = new HashMap>();
                       // Traverse the array and store indices of each word
                       for(int i = 0; i < words.length; i++) {
                           String w = words[i];
                           if(map.containsKey(w)) {
                               map.get(w).add(i);
                           } else {
                               List list = new ArrayList();
                               list.add(i);
                               map.put(w, list);
                           }
                       }
                   }
                   
                   // Function to find the shortest distance between word1 and word2
                   public int shortest(String word1, String word2) {
                       List list1 = map.get(word1); // Get indices of word1
                       List list2 = map.get(word2); // Get indices of word2
                       int ret = Integer.MAX_VALUE; // Initialize result with maximum value
                       
                       // Two pointers to traverse both lists
                       for(int i = 0, j = 0; i < list1.size() && j < list2.size(); ) {
                           int index1 = list1.get(i); // Index of word1
                           int index2 = list2.get(j); // Index of word2
                           
                           if(index1 < index2) {
                               ret = Math.min(ret, index2 - index1); // Update result if smaller distance found
                               i++; // Move pointer in list1
                           } else {
                               ret = Math.min(ret, index1 - index2); // Update result if smaller distance found
                               j++; // Move pointer in list2
                           }
                       }
                       return ret; // Return the shortest distance
                   }
               }
               

Complexity Analysis

Here, N is the number of strings in the list wordsDict.

Time complexity: O(N) for initialization and O(M) for each query.

The initialization step involves traversing the array once to build the map. This takes O(N) time, where N is the number of strings in wordsDict.

For each query, we retrieve indices from the map (which takes O(1) time) and then find the shortest distance using a two-pointer technique. Since the maximum size of lists is proportional to N, the query operation is O(M), where M is the number of indices in the lists for word1 and word2.

Space complexity: O(N).

The space complexity is dominated by the storage of indices in the map, which is proportional to the number of strings in wordsDict. Hence, the space complexity is O(N).