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.
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
Use a dictionary to store the positions for all the unique words. Given word1 and word2, find their positions, and compute the smallest distance.
Complexity 2
Time:O(n+m) where n is the length of the array, m is the maximum of the number of word1 and word2.
Space:O(n)
Solution 2
class WordDistance(object):
def __init__(self, words):
"""
:type words: List[str]
"""
# construct a dictionary to store the position of each word
self.dict = {}
for i, w in enumerate(words):
self.dict[w] = self.dict.get(w, []) + [i]
def shortest(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
a, b = self.dict.get(word1), self.dict.get(word2)
m, n = len(a), len(b)
res = sys.maxsize
i, j = 0, 0
# find the shortest distance
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
# Your WordDistance object will be instantiated and called as such:
# obj = WordDistance(words)
# param_1 = obj.shortest(word1,word2)