One pass and one pointer Python solution, can be directly used for 243 as well


  • 0
    B
    class Solution(object):
        def shortestWordDistance(self, words, word1, word2):
            """
            :type words: List[str]
            :type word1: str
            :type word2: str
            :rtype: int
            """
            result, last = 2**31 - 1, -1
            for i, w in enumerate(words):
                if last != -1 and ((w == word1 and words[last] == word2) or\
                (w == word2 and words[last] == word1)):
                    result = min(result, i - last)
                if w == word1 or w == word2:
                    last = i
            return result
    

    Just one pointer to record last position of word1 or word2. The logic is that if word1 or word2 appears continuously, the earlier one would not be shorter than the later one.

    e.g., W1, W1, W3, W2, W2
    last points to 0 first, and then 1 without updating result, since W1 at 0 would not be closer to W2 than W1 at 1.

    The exact code can be directly used for 243.


Log in to reply
 

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