Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
给一个单词数组和两个单词，返回这两个单词在数组里的最短距离。假定两个单词不同，而且都在数组中。
Java:
public int shortestDistance(String[] words, String word1, String word2) {
int m=-1;
int n=-1;
int min = Integer.MAX_VALUE;
for(int i=0; i<words.length; i++){
String s = words[i];
if(word1.equals(s)){
m = i;
if(n!=-1)
min = Math.min(min, m-n);
}else if(word2.equals(s)){
n = i;
if(m!=-1)
min = Math.min(min, n-m);
}
}
return min;
}
Python:
# Time: O(n)
# Space: O(1) class Solution:
# @param {string[]} words
# @param {string} word1
# @param {string} word2
# @return {integer}
def shortestDistance(self, words, word1, word2):
dist = float("inf")
i, index1, index2 = 0, None, None
while i < len(words):
if words[i] == word1:
index1 = i
elif words[i] == word2:
index2 = i if index1 is not None and index2 is not None:
dist = min(dist, abs(index1 - index2))
i += 1 return dist
C++:
class Solution {
public:
int shortestDistance(vector<string>& words, string word1, string word2) {
int p1 = -1, p2 = -1, res = INT_MAX;
for (int i = 0; i < words.size(); ++i) {
if (words[i] == word1) p1 = i;
else if (words[i] == word2) p2 = i;
if (p1 != -1 && p2 != -1) res = min(res, abs(p1 - p2));
}
return res;
}
};
C++:
class Solution {
public:
int shortestDistance(vector<string>& words, string word1, string word2) {
int idx = -1, res = INT_MAX;
for (int i = 0; i < words.size(); ++i) {
if (words[i] == word1 || words[i] == word2) {
if (idx != -1 && words[idx] != words[i]) {
res = min(res, i - idx);
}
idx = i;
}
}
return res;
}
};
类似题目：
[LeetCode] 244. Shortest Word Distance II 最短单词距离 II
[LeetCode] 245. Shortest Word Distance III 最短单词距离 III