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 and refine your code.

LeetCode 244: Shortest Word Distance II Solution

LeetCode 244 Solution 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.

: :

LeetCode 244 Solutions in Java, C++, Python

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;
    }
}

Interactive Code Editor for LeetCode 244

Improve Your LeetCode 244 Solution

Use the editor below to refine the provided solution for LeetCode 244. Select a programming language and try the following:

Add import statements if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Loading editor...