Problem

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.

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Solution

Method 1 - Two pointers

To find the shortest distance between the occurrences of word1 and word2, we can use a linear scan and keep track of the indices of the last occurrences of these words.

Approach

  • Iterate through wordsDict while keeping two variables to store the indices of the last occurrences of word1 and word2.
  • If word1 equals word2, initiate a variable to store the index of the previous occurrence.
  • Calculate the distance whenever you update these indices and keep track of the minimum distance found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

 public class Solution {
     public int shortestDistance(String[] wordsDict, String word1, String word2) {
         int ans = Integer.MAX_VALUE;
         int p1 = -1, p2 = -1;
 
         for (int i = 0; i < wordsDict.length; i++) {
             if (wordsDict[i].equals(word1)) {
                 p1 = i;
                 if (word1.equals(word2) && p2 != -1) {
                     ans = Math.min(ans, Math.abs(p1 - p2));
                 }
                 p2 = p1;  // Special case where word1 equals word2
             } else if (wordsDict[i].equals(word2)) {
                 p2 = i;
             }
 
             if (p1 != -1 && p2 != -1 && !word1.equals(word2)) {
                 ans = Math.min(ans, Math.abs(p1 - p2));
             }
         }
         return ans;
     }
 }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        ans: int = float("inf")
        p1: int = -1
        p2: int = -1
        same_word: bool = word1 == word2

        for i, word in enumerate(wordsDict):
            if word == word1:
                p1 = i
                if same_word and p2 != -1:
                    ans = min(ans, abs(p1 - p2))
                p2 = p1  # Special case: handling same word
            elif word == word2:
                p2 = i
            
            if p1 != -1 and p2 != -1 and not same_word:
                ans = min(ans, abs(p1 - p2))
                
        return ans

Complexity

  • ⏰ Time complexity: O(n) because we only need to iterate through wordsDict once.
  • 🧺 Space complexity: O(1) since we only use a few variables to store indices and the minimum distance.