# Time:  init: O(n), lookup: O(a + b), a, b is occurences of word1, word2
# Space: O(n)
#
# This is a follow up of Shortest Word Distance.
# The only difference is now you are given the list of words
# and your method will be called repeatedly many times with different parameters.
# How would you optimize it?
#
# Design a class which receives a list of words in the constructor,
# and implements a method that takes two words word1 and word2 and
# return the shortest distance between these two words in the list.
#
# For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
#
# Given word1 = “coding”, word2 = “practice”, return 3.
# Given word1 = "makes", word2 = "coding", return 1.
#
# Note: You may assume that word1 does not equal to word2,
# and word1 and word2 are both in the list.
#

from collections import defaultdict

class Solution:
    # initialize your data structure here.
    # @param {string[]} words

    def __init__(self, words):
        self.wordIndex = defaultdict(list)
        for i in xrange(len(words)):
            self.wordIndex[words[i]].append(i)

    def shortest(self, word1, word2):
        indexes1 = self.wordIndex[word1]
        indexes2 = self.wordIndex[word2]

        i, j, dist = 0, 0, float("inf")
        while i < len(indexes1) and j < len(indexes2):
            dist = min(dist, abs(indexes1[i] - indexes2[j]))
            if indexes1[i] < indexes2[j]:
                i += 1
            else:
                j += 1

        return dist
        
