3 problems are from leetcode.
WordDistanceI
Given a list of words and two words word1 and word2, 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.
Solution. This is a easy one. We maintain an index for the position where the last word is. We just go through words[] one time and update min and index.
Check my code on github: link
WordDistanceII
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.
Solution. Popular solution is to use HashMap and ArrayList. For each word, it maintains a list. Put the index where this word happened in list. In this way, the list has ascending order. When we compare 2 words distance, we try to find the min value between 2 lists. This is discussed in this post. This solution takes O(n) time for building structure, O(n) time for searching min distance.
Another idea is that we put all combination of 2 words in the HashMap, in this way, we can get the result in O(1) time. This solution takes O(n^2) time for building the structure.
Check my code on github: link
WordDistanceIII
This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
word1 and word2 may be the same and they represent two individual words in the list.
Solution. This one can be easily derived from WordDistanceI. We change to calculate distance when 2 words are equal.
Because I didn’t purchase leetcode, I’m not sure if this question is also applied to WordDistanceII. If it is, the change is not hard neither.
Check my code on github: link