https://leetcode.com/problems/shortest-word-distance-ii/
Shortest Word Distance II
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.
Code
class WordDistance(object):
def __init__(self, words):
"""
initialize your data structure here.
:type words: List[str]
"""
word_dic = dict()
for i in xrange(len(words)):
w = words[i]
if word_dic.get(w, None):
word_dic[w].append(i)
else:
word_dic[w] = [i]
self.word_dic = word_dic
def shortest(self, word1, word2):
"""
Adds a word into the data structure.
:type word1: str
:type word2: str
:rtype: int
"""
l1 = self.word_dic[word1]
l2 = self.word_dic[word2]
min_dis = sys.maxint
p1 = 0
p2 = 0
while p1 < len(l1) and p2 < len(l2):
min_dis = min(min_dis, abs(l1[p1]-l2[p2]))
if min_dis == 1:
return 1
if l1[p1] > l2[p2]:
p2 += 1
else:
p1 += 1
return min_dis
# Your WordDistance object will be instantiated and called as such:
# wordDistance = WordDistance(words)
# wordDistance.shortest("word1", "word2")
# wordDistance.shortest("anotherWord1", "anotherWord2")
Idea
Since the function `shortest` will be called repeatedly, we need to use more space in trade of less time. We know from the previous post that if we don’t use any space we can have an O(N) algorithm. Therefore, in this problem, we want to achieve shorter time than O(N) by using more space.
What we do is just using a dictionary to store positions for words. (key: word, value: a list of positions in `words` where the word appears). Since we traverse from words[0] to words[-1], we guarantee every position list stores positions in an ascending order. Then, when we call `shortest(words, word1, word2)`. we extract `word1`’s and `word2`’s position lists.
The crux of the algorithm is that if p1 (a position from word1’s position list) is already larger than p2 (a position from word2’s position list), then every position after p1 in the word1’s position list will have larger distance with p2. Therefore, you don’t need to compare those positions after p1 anymore. Instead, you increase p2 in order to let it be closer to p1.
The time complexity is O(m+n) where m and n are the lengths of l1 and l2.
Reference: https://discuss.leetcode.com/topic/20643/java-solution-using-hashmap