245. Shortest Word Distance III

Approach 1: Storing list of indices of both words

class Solution(object):
    def shortestWordDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """
        word1s = []
        word2s = []
        for i in range(len(words)):
            if words[i] == word1:
                word1s.append(i)
            if words[i] == word2:
                word2s.append(i)
        mi = float('inf')
        for i in word1s:
            for j in word2s:
                if i != j:
                    mi = min(abs(i-j), mi)
        return mi

For both the words we store the indices of all the positions they occur in. Once we have that we can easily iterate through both of these individual lists and find the minimum difference

Time Complexity: O(N^2)

Space Complexity: O(N)

Approach 2: Iterating through list but storing only last seen index of each word

class Solution(object):
    def shortestWordDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """
        idx1 = idx2 = res = float('inf')
        if word1 == word2:
            for i,word in enumerate(words):
                if word == word1:
                    idx1 = idx2 
                    idx2 = i
                    res = min(res,abs(idx2-idx1))
        else:
            for i,word in enumerate(words):
                if word == word1:
                    idx1 = i
                    res = min(res,abs(idx1-idx2))
                elif word == word2:
                    idx2 = i
                    res = min(res,abs(idx1-idx2))
        return res

In this approach instead of storing lists of indices we just need to store the last seen one. Each time we see one of the words we just calculate the difference between the two last seen indices and update it if it smaller than the shortest distance we've seen before

Time Complexity: O(N)

Space Complexity: O(1)