LeetCode 244: Shortest Word Distance II Solution

Master LeetCode problem 244 (Shortest Word Distance II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

244. Shortest Word Distance II

Medium

Array Hash Table Two Pointers String Design

Problem Explanation

Explanation:

This problem requires us to design a class WordDistance that will be initialized with a list of words. The class should have a method shortest that will return the shortest distance between two given words in the list of words.

To solve this problem efficiently, we can pre-process the list of words and store their indices in a hashmap. Then, for each pair of words, we can find their respective indices from the hashmap and calculate the minimum distance between them.

Algorithm:

Create a hashmap to store the indices of each word in the list.
Initialize the hashmap by iterating through the list of words and storing their indices.
In the shortest method, obtain the indices of the two words from the hashmap.
Use two pointers to iterate through the two lists of indices and calculate the minimum distance.

Time Complexity:

Preprocessing: O(n) where n is the number of words in the list.
Shortest method: O(m + n) where m is the number of occurrences of the first word and n is the number of occurrences of the second word.

Space Complexity:

O(n) where n is the number of words in the list.

: :

Solution Code

class WordDistance {
    Map<String, List<Integer>> wordIndices;

    public WordDistance(String[] words) {
        wordIndices = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            wordIndices.computeIfAbsent(words[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> indices1 = wordIndices.get(word1);
        List<Integer> indices2 = wordIndices.get(word2);

        int minDistance = Integer.MAX_VALUE;
        int i = 0, j = 0;

        while (i < indices1.size() && j < indices2.size()) {
            minDistance = Math.min(minDistance, Math.abs(indices1.get(i) - indices2.get(j)));
            if (indices1.get(i) < indices2.get(j)) {
                i++;
            } else {
                j++;
            }
        }

        return minDistance;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 244 (Shortest Word Distance II)?

This page provides optimized solutions for LeetCode problem 244 (Shortest Word Distance II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 244 (Shortest Word Distance II)?

The time complexity for LeetCode 244 (Shortest Word Distance II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 244 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 244 in Java, C++, or Python.

Back to LeetCode Solutions