Python short solution 92ms using dict

• ``````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])``````

• 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/java-solution-using-minimum-difference-between-sorted-arrays), where the time complexity is O(m+n).

• Thank you, that solution is much smarter than mine.

• 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
``````

• Yes. I think this is due to for loops run faster than while loops in Python. And Leetcode's test case are relatively small so the run time complexity doesn't compensate the gap.

• self.dic[w] = self.dic.get(w, []) + [index]

self.dic[w] = self.dic.get(w, []) + [index]
Is there anyone can help me explain this?

• hmm, i have a ruby version of this and it runs into time complexity issues.

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