Shortest Word Distance

Problem Summary

• Given an array of words and two input words
• Return the shortest distance between the two words

Key Observations

• Duplicate words are allowed

Main Concepts Used

• Array
• Two Pointers

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through the array once
• Space: $O(1)$ → Reason: Not storing a copy

Code

class Solution:
    def shortestDistance(self, words, word1, word2):
        indexWord1 = None
        indexWord2 = None
        minDistance = float("inf")

        for i, word in enumerate(words):
            if word == word1:
                indexWord1 = i
            elif word == word2:
                indexWord2 = i

            if indexWord1 != None and indexWord2 != None:
                minDistance = min(abs(indexWord1 - indexWord2), minDistance)
        return minDistance

Common Mistakes / Things I Got Stuck On

• if indexWord1 and indexWord2: would fail if index is 0.
• Explicit checks are needed when the value could be $0$