博文中会简要介绍Leetcode P0244题目分析及解题思路。
“Shortest Word Distance II”是一道中等难度的题目，是p0243的衍生题，主要思路是运用哈希表和双指针的思想。
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. Your method will be called repeatedly many times with different parameters.
Example: Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].
Input: word1 = “coding”, word2 = “practice” Output: 3 Input: word1 = "makes", word2 = "coding" Output: 1Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
这道题的核心抓手在于，给定两个单词，我们实际上只需要知道这两个单词的所有出现过的位置，就可以得到这两个单词之间的最小距离，无需遍历整个words数组，而这样一来就可以大大减小反复调用shortest函数产生的代价。
我们首先使用类似哈希表存储位置信息，这个时间复杂度是O(n)。如果后续逐一比较得到最小距离，则又需要O(n^2)的时间复杂度。但需要注意的是，我们在存储位置信息时，每一个位置表都是默认有序的，所以实际上我们可以利用双指针得到线性时间复杂度的后续算法。
我们分别用p1和p2来遍历word1和word2的位置表，两个单词的位置表都是有序的。我们可以按下图所示，寻找最小距离。
idxList1: 1, 3, 6, 8, 12
|
p1
idxList2: 2, 5, 7, 9
|
p2
显然idxList1[p1] < idxList2[p2]，currDist = 1
idxList1: 1, 3, 6, 8, 12
|
p1
idxList2: 2, 5, 7, 9
|
p2
若向后移动p2，则一定会有dist = 4 > currDist，也就是说此时向后移动p2得到的距离一定比currDist大，所以下一次寻找最小距离，应当移动p1
idxList1: 1, 3, 6, 8, 12
|
p1
idxList2: 2, 5, 7, 9
|
p2
这样一来，才有可能出现dist < currDist的情况。然后反复执行上述操作即可。
那么不难得出，如果p1指向的位置小于p2指向的位置，则向后移动p2得到的新p2与旧p1指向的位置之间的差显然大于当前p1和p2指向的位置之间的差。所以下一次移动将向后移动p1去寻找可能的更小距离。反之，如果p2指向的位置小于p1指向的位置，则应当向后移动p2。
以下是Java的题解代码实现。
class WordDistance {
private Map<String, List<Integer>> word2IdxMap = new HashMap<>();
public WordDistance(String[] words) {
for (int idx=0; idx<words.length; ++idx) {
if (!word2IdxMap.containsKey(words[idx])) {
word2IdxMap.put(words[idx], new ArrayList<>());
}
word2IdxMap.get(words[idx]).add(idx);
}
}
public int shortest(String word1, String word2) {
// Location lists for both the words
// the indices will be in SORTED order by default
List<Integer> idxList1 = this.word2IdxMap.get(word1), idxList2 = this.word2IdxMap.get(word2);
int p1 = 0, p2 = 0, minDist = Integer.MAX_VALUE;
int N1 = idxList1.size(), N2 = idxList2.size();
while (p1 < N1 && p2 < N2) {
minDist = Math.min(minDist, Math.abs(idxList1.get(p1)-idxList2.get(p2)));
if (idxList1.get(p1) < idxList2.get(p2)) {
++p1;
}
else {
++p2;
}
}
return minDist;
}
}
/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance obj = new WordDistance(words);
* int param_1 = obj.shortest(word1,word2);
*/
以下是C++的题解代码实现。
class WordDistance {
public:
WordDistance(vector<string>& words) {
for (int idx=0; idx<words.size(); ++idx) {
word2idx[words[idx]].push_back(idx);
}
}
int shortest(string word1, string word2) {
vector<int> loc1 = word2idx[word1], loc2 = word2idx[word2];
int p1 = 0, p2 = 0, min_dist = INT_MAX;
while (p1 < loc1.size() && p2 < loc2.size()) {
min_dist = min(min_dist, abs(loc1[p1]-loc2[p2]));
if (loc1[p1] < loc2[p2]) {
++p1;
}
else {
++p2;
}
};
return min_dist;
}
private:
unordered_map<string, vector<int>> word2idx;
};
/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance* obj = new WordDistance(words);
* int param_1 = obj->shortest(word1,word2);
*/