Python O(n) init O(n) query solution


  • 0
    class WordDistance(object):
        def __init__(self, words):
            self.dic = {}
            for i, word in enumerate(words):
                self.dic[word] = self.dic.get(word, []) + [i]
    
        def shortest(self, word1, word2):
            p1 = p2 = 0
            min_dist = sys.maxint
            arr1 = self.dic[word1]
            arr2 = self.dic[word2]
            while p1 < len(arr1) and p2 < len(arr2):
                min_dist = min(min_dist, abs(arr1[p1] - arr2[p2]))
                if arr1[p1] < arr2[p2]:
                    p1 += 1
                else:
                    p2 += 1
            return min_dist
    

Log in to reply
 

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