244. Shortest Word Distance II

#hash-table #counting

Problem

Shortest Word Distance II - LeetCodeLeetCode

``

Intuition

Time Complexity

Space Complexity

Solution

class WordDistance {
    // Map to store the positions of words in the input dictionary
    private Map<String, List<Integer>> map = new HashMap<>();

    public WordDistance(String[] wordsDict) {
        // Build the map by iterating through the words in the dictionary
        for (int i = 0; i < wordsDict.length; i++) {
            String word = wordsDict[i];
            // If the word is encountered for the first time, add an empty list for its positions
            map.putIfAbsent(word, new ArrayList<>());
            // Add the current position of the word to its list of positions
            map.get(word).add(i);
        }
    }

        public int shortest(String word1, String word2) {
            // m = size of posistions for word1
            // n = size of positions for word2
            // Time Complexity: O(m + n)

            // Space Complexity: O(1), auxillary space. No extra space is required
            // Retrieve the lists of positions for the two input words from the map
            List<Integer> d1 = map.get(word1);
            List<Integer> d2 = map.get(word2);
            
            // Initialize two pointers for iterating through the positions of the words
            int i = 0, j = 0;
            
            // Initialize the shortest distance to a large value
            int shortest = Integer.MAX_VALUE;
            
            // Iterate through the positions of the words to find the minimum distance
            while (i < d1.size() && j < d2.size()) {
                // Get the current positions of word1 and word2
                int r1 = d1.get(i);
                int r2 = d2.get(j);
                
                // Calculate the absolute difference between the positions and keep track of 
                // shortest distances
                shortest = Math.min(shortest, Math.abs(r1 - r2));
                
                // Move the pointer that corresponds to the smaller position
                if (r1 < r2) {
                    i++;
                } else {
                    j++;
                }
            }
            
            // Return the shortest distance
            return shortest;
    }
}