class WordDistance:
def __init__(self, words):
self.dic = {}
for index, w in enumerate(words):
self.dic[w] = self.dic.get(w, []) + [index]
def shortest(self, word1, word2):
return min(abs(i1  i2) for i1 in self.dic[word1] for i2 in self.dic[word2])
Python short solution 92ms using dict

The solution is not bad while the time complexity of shortest( ) function here is O(m*n), you can refer to this solution (https://leetcode.com/discuss/50185/javasolutionusingminimumdifferencebetweensortedarrays), where the time complexity is O(m+n).

Modified shortest() method to O(m + n) as caikehe mentioned in the comment, But the running time becomes bigger, about 110~130ms.
class WordDistance: def __init__(self, words): self.dic = {} for index, w in enumerate(words): self.dic[w] = self.dic.get(w, []) + [index] def shortest(self, word1, word2): i1,i2,distance = 0,0,sys.maxint while i1 < len(self.dic[word1]) and i2 < len(self.dic[word2]): distance = min(distance, abs(self.dic[word1][i1]self.dic[word2][i2])) # Move the smaller one forward if self.dic[word1][i1] > self.dic[word2][i2]: i2 += 1 else: i1 += 1 return distance

@aimee9098 said in Python short solution 92ms using dict:
self.dic[w] = self.dic.get(w, []) + [index]
self.dic[w] = self.dic.get(w, []) + [index]
Is there anyone can help me explain this?