Short'n'Clean O(n) init, O(n) query in Python


  • 9
    class WordDistance(object):
        def __init__(self, words):
            self.d = {}
            for i, w in enumerate(words):
                self.d[w] = self.d.get(w, []) + [i]
    
        def shortest(self, w1, w2):
            a, b = self.d[w1], self.d[w2]
            m, n, i, j, res = len(a), len(b), 0, 0, sys.maxsize
            while i < m and j < n:
                res = min(res, abs(a[i] - b[j]))
                if a[i] < b[j]:
                    i += 1
                else:
                    j += 1
            return res

  • 0

    @agave great solution. Learn a lot from you!


Log in to reply
 

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