The Venture of San Francisco

[LeetCode] Shortest Word Distance

Posted on Edited on In Disqus:

Question:
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

1
2
Input: word1 = “coding”, word2 = “practice”
Output: 3
1
2
Input: word1 = "makes", word2 = "coding"
Output: 1

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Analysis:

This one is pretty straightforward. You can use two different word indices to represent word1 and word2 by given a single for-loop to find out these two different indices. The difference between these two indices would be the distance between word1 and word2. You need to compare different distances to get the shortest one. That one would be our answer. So, the runtime complexity would be O(n) because you need to run through all elements in this word dictionary. And, the space complexity would be O(1) because we only need three variables to memorize the word indices and the result. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
  public int shortestDistance(String[] words, String word1, String word2) {
    int wordIndex1 = -1, wordIndex2 = -1; 
    int minDistance = Integer.MAX_VALUE; 
    
    for (int i = 0; i < words.length; i++) {
      if (words[i].equals(word1)) wordIndex1 = i; 
      if (words[i].equals(word2)) wordIndex2 = i; 
      
      if (wordIndex1 != -1 && wordIndex2 != -1) {
        if (minDistance > Math.abs(wordIndex1 - wordIndex2)) {
          minDistance = Math.abs(wordIndex1 - wordIndex2);
        }
      }
    }
    return minDistance;
  }
}