Problem
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.
Solution
用一個map<string, vector<int>>保存對應(yīng)字符串所在的索引骑科，然后枚舉index[word1]和index[word2]索引值橡淑，記錄最小差值。
class WordDistance {
private:
map<string, vector<int>> index;
public:
WordDistance(vector<string>& words) {
for(int i = 0; i < words.size(); i++) {
index[words[i]].push_back(i);
}
}
int shortest(string word1, string word2) {
int minV = INT_MAX;
for(int i = 0; i < index[word1].size(); i++) {
for(int j = 0; j < index[word2].size(); j++) {
minV = min(abs(index[word1][i] - index[word2][j]), minV);
}
}
return minV;
}
};
優(yōu)化：
- 用
ordered_map咆爽，這里對于元素是否排序并不重要 - 由于是順序掃描梁棠，所以索引應(yīng)該是順序插入同一個字符串的
map中，所以相當于在兩個排序的數(shù)組中找最小差值斗埂。有點類似于2sum的思想符糊。根據(jù)當前索引值，讓值小的那個的數(shù)組指針往后移一位呛凶。
code
class WordDistance {
private:
unordered_map<string, vector<int>> index;
public:
WordDistance(vector<string>& words) {
for(int i = 0; i < words.size(); i++) {
index[words[i]].push_back(i);
}
}
int shortest(string word1, string word2) {
int minV = INT_MAX;
int i = 0;
int j = 0;
int n = index[word1].size();
int m = index[word2].size();
while (i < n && j < m) {
int index1 = index[word1][i];
int index2 = index[word2][j];
if (index1 < index2) {
minV = min(index2 - index1, minV);
i++;
} else {
minV = min(index1 - index2, minV);
j++;
}
}
return minV;
}
};