Python O(n*n) solution with comments.


  • 0
    C
    # O(n*n) time
    def shortestDistance(self, words, word1, word2):
        res = len(words)
        for i in xrange(len(words)):
            if words[i] == word1:
                res = min(res, self.helper(words, i, word2))
        return res
    
    # go from middle point to both sides, 
    # like: https://leetcode.com/problems/longest-palindromic-substring/
    def helper(self, words, i, word2):
        j = 0
        while (i-j<0 or words[i-j]!=word2) and (i+j>=len(words) or words[i+j]!=word2):
            j += 1
        return j

  • 2
    C

    Here is a version which stores the indexes:

    # O(n*n) time, O(n) space   
    def shortestDistance(self, words, word1, word2):
        ind1, ind2 = [], []
        for i, w in enumerate(words):
            if w == word1:
                ind1.append(i)
            elif w == word2:
                ind2.append(i)
        # return min(map(lambda x: abs(x[0]-x[1]), itertools.product(ind1, ind2)))
        # return min(map(lambda x: abs(x[0]-x[1]), ((i, j) for i in ind1 for j in ind2)))
        return min(abs(i-j) for i in ind1 for j in ind2)

Log in to reply
 

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