# 244. Shortest Word Distance II

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: 1
``````

Note:
You may assume that  word1  does not equal to  word2 , and  word1  and  word2  are both in the list.

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

int shortest(string word1, string word2) {
int res = INT_MAX;
for (int i = 0; i < m[word1].size(); ++i) {
for (int j = 0; j < m[word2].size(); ++j) {
res = min(res, abs(m[word1][i] - m[word2][j]));
}
}
return res;
}

private:
unordered_map<string, vector<int> > m;
};
``````

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

int shortest(string word1, string word2) {
int i = 0, j = 0, res = INT_MAX;
while (i < m[word1].size() && j < m[word2].size()) {
res = min(res, abs(m[word1][i] - m[word2][j]));
m[word1][i] < m[word2][j] ? ++i : ++j;
}
return res;
}

private:
unordered_map<string, vector<int> > m;
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/244

Shortest Word Distance

Merge Two Sorted Lists

https://leetcode.com/problems/shortest-word-distance-ii/

https://leetcode.com/problems/shortest-word-distance-ii/discuss/67028/Java-Solution-using-HashMap

https://leetcode.com/problems/shortest-word-distance-ii/discuss/67066/9-line-O(n)-C%2B%2B-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation