Clean python solution, O(n) one pass, 108ms


  • 0
    W
    class Solution(object):
        def shortestWordDistance(self, words, word1, word2):
            """
            :type words: List[str]
            :type word1: str
            :type word2: str
            :rtype: int
            """
            max_index_seen_at = {}
            min_distance = len(words)
            
            for index, word in enumerate(words):
                if word == word1 and word2 in max_index_seen_at:
                    min_distance = min(min_distance, index - max_index_seen_at[word2])
                elif word == word2 and word1 in max_index_seen_at:
                    min_distance = min(min_distance, index - max_index_seen_at[word1])
                
                max_index_seen_at[word] = index
    
            return min_distance
    

    readable code, just keep track of max index you saw for each number thus far


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.