My python O(n) solution, separately consider two cases, beats 80%


  • 0
    Y

    Here is my solution. I explicitly consider two cases: 1) word1 = word2 and 2) word1 != word2. Any comments on improvement?

    class Solution(object):
        def shortestWordDistance(self, words, word1, word2):
            """
            :type words: List[str]
            :type word1: str
            :type word2: str
            :rtype: int
            """
            word1_idx, word2_idx, n = float("inf"), float("inf"), len(words)
            dist = n - 1
            if word1 == word2:
                for i in xrange(n):
                    if words[i] == word1:
                        dist = min(dist, abs(i - word1_idx))
                        word1_idx = i
                return dist
            else:
                for i in xrange(n):
                    if words[i] == word1:
                        word1_idx = i
                    elif words[i] == word2:
                        word2_idx = i
                    dist = min(dist, abs(word1_idx - word2_idx))
                return dist
    

Log in to reply
 

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