-
Notifications
You must be signed in to change notification settings - Fork 3
/
245.cpp
32 lines (31 loc) · 1001 Bytes
/
245.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
int n = wordsDict.size();
unordered_map<string, vector<int>> mp;
for (int i = 0; i < n; ++i) {
mp[wordsDict[i]].push_back(i);
}
int res = INT_MAX;
if (word1 == word2) {
const vector<int>& v = mp[word1];
int m = v.size();
for (int i = 1; i < m; ++i) {
res = min(res, v[i] - v[i - 1]);
}
}
else {
const vector<int>& v1 = mp[word1];
const vector<int>& v2 = mp[word2];
int idx1 = 0;
int idx2 = 0;
while (idx1 < v1.size() && idx2 < v2.size()) {
res = min(res, abs(v1[idx1] - v2[idx2]));
if (v1[idx1] > v2[idx2]) idx2++;
else if (v1[idx1] < v2[idx2]) idx1++;
else break;
}
}
return res;
}
};