C++_Linear Time Complexity O(n)_AC_98.72%_42ms

• Here is the new question：given two sorted vectors，we want：min(abs(vec2[j] - vec1[i])) for all i and j. Time complexity: Linear.

Because vec1 and vec2 are sorted, so if vec2[j] > vec1[i], so we want to reduce the difference between them, we need to increase vec1[i], so we add 1 to i;
else we will add 1 to j.

``````class WordDistance {
unordered_map<string, vector<int>> mp;
public:
WordDistance(vector<string>& words) {
for(int i = 0; i < words.size(); ++i){
mp[words[i]].push_back(i);
}
}

int shortest(string word1, string word2) {
vector<int> vec1 = mp[word1];
vector<int> vec2 = mp[word2];
int res = INT_MAX;
int i = 0, j = 0;
//Here is the new question：given two sorted vectors，we want：min(abs(vec2[j] - vec1[i])) for all i and j. Time complexity: Linear
while(i < vec1.size() && j < vec2.size()){
res = min(res, abs(vec2[j] - vec1[i]));
if(vec2[j] > vec1[i]){
i++;
}else{j++;}
}
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.