Python solution O(n) time, O(1) space


  • 9
    A
    def shortestDistance(self, words, word1, word2):
        size = len(words)
        index1, index2 = size, size
        ans = size
        
        for i in xrange(size):
            if words[i] == word1:
                index1 = i
                ans = min(ans, abs(index1-index2))
            elif words[i] == word2:
                index2 = i
                ans = min(ans, abs(index1-index2))
        return ans

  • 1

    only one index is needed

        def shortestDistance(self, words, word1, word2):
            ans = len(words)
            current_word, current_index = None, 0
            for index, word in enumerate(words):
                if word != word1 and word != word2: continue
                if current_word and word != current_word:
                    ans = min(ans, index - current_index)
                current_word, current_index = word, index
            return ans
    

  • 1
    A

    Same logic, slightly different implementation. Beats 92%

    class Solution(object):
        def shortestDistance(self, words, word1, word2):
            """
            :type words: List[str]
            :type word1: str
            :type word2: str
            :rtype: int
            """
            w1i, w2i = words.index(word1), words.index(word2)
            d = abs(w1i - w2i)
            for i, word in enumerate(words):
                if word == word1:
                    w1i = i
                    if abs(i - w2i) < d:
                        d = abs(i - w2i)
                elif word == word2:
                    w2i = i
                    if abs(i - w1i) < d:
                        d = abs(i - w1i)
            return d
    

  • 0
    L

    @autekwing even simpler:

    class Solution(object):
        def shortestDistance(self, words, word1, word2):
            """
            :type words: List[str]
            :type word1: str
            :type word2: str
            :rtype: int
            """
            m=len(words)
            p1=-len(words)
            p2=len(words)
            for i in xrange(len(words)):
                if words[i]==word1:
                    p1=i
                elif words[i]==word2:
                    p2=i
                m=min(m,abs(p1-p2))
            return m

  • 0
    G

    for each loop we can check if min ==1, then directly return 1


Log in to reply
 

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