Skip to main content

Shortest Word Distance II Solution

In this tutorial, we will solve the Shortest Word Distance II problem using a design approach with a hash table. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, and C++.

Problem Description​

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.

Examples​

Example 1:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

Example 2:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

Constraints​

  • 1≤wordsDict.length≤3×1041 \leq \text{wordsDict.length} \leq 3 \times 10^4
  • 1≤wordsDict[i].length≤101 \leq \text{wordsDict[i].length} \leq 10
  • wordsDict[i] consists of lowercase English letters.
  • word1 and word2 are both in wordsDict.
  • word1 != word2.

Solution for Shortest Word Distance II​

Intuition and Approach​

We can solve this problem efficiently by pre-processing the words dictionary and storing the indices of each word in a hash table. This allows us to quickly find the shortest distance between any two given words by comparing their indices.

Approach: Using Hash Table​

The hash table approach involves pre-processing the wordsDict to store the indices of each word. When we need to find the shortest distance between two words, we retrieve their indices from the hash table and calculate the minimum distance.

Implementation​

Live Editor
function shortestWordDistanceII() {
  class WordDistance {
    constructor(wordsDict) {
      this.wordMap = new Map();
      for (let i = 0; i < wordsDict.length; i++) {
        if (!this.wordMap.has(wordsDict[i])) {
          this.wordMap.set(wordsDict[i], []);
        }
        this.wordMap.get(wordsDict[i]).push(i);
      }
    }

    shortest(word1, word2) {
      const indices1 = this.wordMap.get(word1);
      const indices2 = this.wordMap.get(word2);
      let i = 0;
      let j = 0;
      let minDistance = Infinity;

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

      return minDistance;
    }
  }

  const wordsDict = ["practice", "makes", "perfect", "coding", "makes"];
  const wordDistance = new WordDistance(wordsDict);
  const result = wordDistance.shortest("coding", "practice");

  return (
    <div>
      <p>
        <b>Input:</b> wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
      </p>
      <p>
        <b>Output:</b> {result}
      </p>
    </div>
  );
}
Result
Loading...

Codes in Different Languages​

Written by @aryansh-patel
 class WordDistance {
constructor(wordsDict) {
this.wordMap = new Map();
for (let i = 0; i < wordsDict.length; i++) {
if (!this.wordMap.has(wordsDict[i])) {
this.wordMap.set(wordsDict[i], []);
}
this.wordMap.get(wordsDict[i]).push(i);
}
}

shortest(word1, word2) {
const indices1 = this.wordMap.get(word1);
const indices2 = this.wordMap.get(word2);
let i = 0;
let j = 0;
let minDistance = Infinity;

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

return minDistance;
}
}

Complexity Analysis​

  • Time Complexity: O(n+k)O(n + k), where n is the number of words in wordsDict and k is the number of queries.
  • Space Complexity: O(n)O(n), where n is the number of words in wordsDict.
  • The time complexity for preprocessing is O(n)O(n) because we iterate through all the words once.
  • The space complexity is O(n)O(n) because we store the indices of each word in a hash table.
  • The time complexity for each query is O(k)O(k), where k is the length of the indices list for the words.
Note

The hash table approach is efficient and recommended for this problem due to its linear preprocessing time complexity and efficient query handling.


Video Explanation of Shortest Word Distance II​