Skip to main content

Shortest Distance Between Words -III

Problem Statement​

  • Given an array of strings wordsDict and two strings that already exist in the array word1 and word2, return the shortest distance between the occurrence of these two words in the list.

  • Note: that word1 and word2 may be the same. It is guaranteed that they represent two individual words in the list.

Example 1:​

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

Example 2:​

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

Solution​

Approach​

  1. Initialization:

    • Initialize two variables to store the most recent positions of word1 and word2.
    • Initialize a variable to store the minimum distance, set it to a large value initially.
  2. Single Pass through the List:

    • Iterate through the list, and for each word:
      • If the word is word1, update the most recent position of word1.
      • If the word is word2, update the most recent position of word2.
      • If both words are the same, ensure you handle the same word case properly.
    • Calculate the distance between the most recent positions of word1 and word2 and update the minimum distance if the calculated distance is smaller.
  3. Output:

    • After iterating through the list, the minimum distance variable will hold the shortest distance between the two words.

Codes in Different Languages​

Written by @sivaprasath
function shortestDistance(wordsDict, word1, word2) {
let pos1 = -1;
let pos2 = -1;
let minDistance = Infinity;

for (let i = 0; i < wordsDict.length; i++) {
if (wordsDict[i] === word1) {
pos1 = i;
if (word1 === word2) {
pos2 = pos1;
}
if (pos2 !== -1) {
minDistance = Math.min(minDistance, Math.abs(pos1 - pos2));
}
} else if (wordsDict[i] === word2) {
pos2 = i;
if (pos1 !== -1) {
minDistance = Math.min(minDistance, Math.abs(pos1 - pos2));
}
}
}

return minDistance;
}

// Example usage:
const wordsDict1 = ["practice", "makes", "perfect", "coding", "makes"];
const word1 = "makes";
const word2 = "coding";
console.log(shortestDistance(wordsDict1, word1, word2)); // Output: 1

const wordsDict2 = ["practice", "makes", "perfect", "coding", "makes"];
const word1Same = "makes";
const word2Same = "makes";
console.log(shortestDistance(wordsDict2, word1Same, word2Same)); // Output: 3

Explanation:​

  • Initialization: pos1 and pos2 are initialized to -1 to indicate that the positions of word1 and word2 have not been found yet. minDistance is set to Infinity to ensure any found distance will be smaller.
  • Single Pass: We iterate through the list, and for each occurrence of word1 or word2, we update the respective positions.
  • Distance Calculation: If both positions have been updated at least once, we calculate the distance and update minDistance if the new distance is smaller.
  • Handling Same Words: If word1 is the same as word2, we set pos2 to pos1 whenever word1 is found to ensure we calculate the distance correctly between different occurrences of the same word.

Complexity​

  • O(n): The solution involves a single pass through the list wordsDict, where n is the length of the list. During this pass, each element is checked and possibly used to update positions and compute distances, which are all O(1) operations.

  • O(1): The solution uses a constant amount of extra space, regardless of the input size. It only maintains a few integer variables (pos1, pos2, minDistance) to store indices and distances. There are no data structures whose size grows with the input.

References​

Author:

Loading...