题目:
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.
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
思路:
注意到word1和word2有可能在字典里面出现多次,我们可以用哈希表保存一个单词的多个位置,然后枚举最小距离。假设word1在words中出现了m次,word2在words中出现了n次,则枚举需要O(m*n)的时间复杂度,可是由于位置索引都是单调递增的,所以我们可以采用一个小技巧将时间复杂度降低到O(m+n)。这里卖个关子,大家看看下面的代码实现^_^。
代码:
class Solution {
public:
int shortestDistance(vector<string>& words, string word1, string word2) {
unordered_map<string, vector<int>> hash;
for (int i = 0; i < words.size(); ++i) {
hash[words[i]].push_back(i);
}
int i = 0, j = 0, ret = INT_MAX;
while (i < hash[word1].size() && j < hash[word2].size()) {
ret = min(ret, abs(hash[word1][i] - hash[word2][j]));
hash[word1][i] < hash[word2][j] ? ++i : ++j;
}
return ret;
}
};