博文中会简要介绍Leetcode P0245题目分析及解题思路。
“Shortest Word Distance III”是一道比较简单的题目，同样是p0243的衍生题，主要思路是运用双指针的思想。
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: 3Note:
You may assume word1 and word2 are both in the list.
这道题和p0243的唯一区别在于给定的两个单词可以相同。只需要分类讨论即可，若两个单词不一样，则思路与p0243一致；若相同，则遍历一遍给定的单词的两个副本（不同位置）的最小距离即可。
以下是Java的题解代码实现。
class Solution {
public int shortestWordDistance(String[] words, String word1, String word2) {
this.words = words;
if (word1.equals(word2)) {
return this.shortestDistanceWithSameWord(word1);
}
else {
return this.shortestDistanceWithDifferenctWords(word1, word2);
}
}
private String[] words = null;
private int shortestDistanceWithDifferenctWords(String word1, String word2) {
int p1 = -1, p2 = -1, N = this.words.length, minDist = N;
for (int idx=0; idx<N; ++idx) {
if (this.words[idx].equals(word1)) {
p1 = idx;
if (p2 != -1)
minDist = Math.min(minDist, Math.abs(p1-p2));
}
else if (this.words[idx].equals(word2)) {
p2 = idx;
if (p1 != -1)
minDist = Math.min(minDist, Math.abs(p1-p2));
}
}
return minDist;
}
private int shortestDistanceWithSameWord(String word) {
int prev = -1, N = words.length, minDist = N;
for (int idx=0; idx<N; ++idx) {
if (words[idx].equals(word)) {
if (prev != -1)
minDist = Math.min(minDist, idx-prev);
prev = idx;
}
}
return minDist;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int shortestWordDistance(vector<string>& words, string word1, string word2) {
this->words_ = words;
if (word1 == word2) {
return _Shortest(word1);
}
else {
return _Shortest(word1, word2);
}
}
private:
vector<string> words_;
int _Shortest(string w1, string w2) {
int p1 = -1, p2 = -1, N = words_.size(), min_dist = N;
for (int idx=0; idx<N; ++idx) {
if (words_[idx] == w1) {
p1 = idx;
min_dist = (p2 != -1)? min(min_dist, abs(p1-p2)): min_dist;
}
else if (words_[idx] == w2) {
p2 = idx;
min_dist = (p1 != -1)? min(min_dist, abs(p1-p2)): min_dist;
}
}
return min_dist;
}
int _Shortest(string w) {
int prev = -1, N = words_.size(), min_dist = N;
for (int idx=0; idx<N; ++idx) {
if (words_[idx] == w) {
if (prev != -1)
min_dist = min(min_dist, idx-prev);
prev = idx;
}
}
return min_dist;
}
};