# 245. Shortest Word Distance III 最短单词距离 III

@TOC

## # 题目描述

Given a list of words and two words `word1` and `word2`, return the shortest distance between these two words in the list.

`word1` and `word2` may be the same and they represent two individual words in the list.

Example:

``````Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “makes”, word2 = “coding”
Output: 1
Input: word1 = "makes", word2 = "makes"
Output: 3
``````

Note:

• You may assume word1 and word2 are both in the list.

## # 题目大意

word1 和 word2 是有可能相同的，并且它们将分别表示为列表中两个独立的单词。

## # 解题方法

### # 字典+暴力检索

1. 如果两个单词不同，那么直接暴力检索这两个的所有坐标的差值绝对值，找最小的。
2. 如果两个单词相同，那么相当于从一个有序数组中找到相邻数字的最小差值，需要一次遍历。

C++代码如下：

``````class Solution {
public:
int shortestWordDistance(vector<string>& words, string word1, string word2) {
unordered_map<string, vector<int>> m;
for (int i = 0; i < words.size(); ++i) {
m[words[i]].push_back(i);
}
int res = INT_MAX;
if (word1 != word2) {
for (int i : m[word1]) {
for (int j : m[word2]) {
res = min(res, abs(i - j));
}
}
} else {
for (int i = 1; i < m[word1].size(); ++i) {
res = min(res, m[word1][i] - m[word1][i - 1]);
}
}
return res;
}
};
``````

## # 日期

2019 年 9 月 24 日 —— 梦见回到了小学，小学已经芳草萋萋破败不堪