[LeetCode] Shortest Word Distance III

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

word1 and word2 may be the same, and they represent two individual words in the list.

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

Input: word1 = “makes”, word2 = “coding”
Output: 1

Input: word1 = "makes", word2 = "makes"
Output: 3

Note:
You may assume word1 and word2 are both on the list.

Analysis:

This quiz is another derived question from Shortest Word Distance. The most significant difference is that the word1 could be the same as word2. There is only one edge case you need to consider:

• If the word dictionary has only the same elements, for example, [“ABC”, “ABC”]

Let’s see how to solve this question.

class Solution {
  fun shortestWordDistance(
    words: Array<String>, 
    word1: String, 
    word2: String
  ): Int {
    if (words.size == 0) return -1

    // step1, initialize word indices and the answer
    var w1: Int = -1
    var w2: Int = -1 
    var distance = Int.MAX_VALUE 

    words.forEachIndexed { i, w -> 
      if(w.equals(word1)) { 
        w1 = i 
        if (w2 != -1) {
          distance = Math.min(distance, Math.abs(w1-w2))
        }
      }
      // Step2. test the edge case. 
      if (w.equals(word2)) {
        w2 = i 
        if (w1 != -1 && w1 != w2) {
          distance = Math.min(distance, Math.abs(w1-w2))
        }
      }
    }

    return distance
  }
}

The time complexity of this class is O(n) because you need to run through all the elements. The space complexity is O(1).