Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
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.
https://www.lintcode.com/problem/shortest-word-distance/description
我的答案：用两个indexes追踪两个words，只有当某个index变化的时候，才要重新计算一次
class Solution {
public:
/**
* @param words: a list of words
* @param word1: a string
* @param word2: a string
* @return: the shortest distance between word1 and word2 in the list
*/
int shortestDistance(vector<string> &words, string &word1, string &word2) {
// Write your code here
int index1 = INT_MAX;
int index2 = INT_MAX;
int ans = INT_MAX;
int len = words.size();
for (int i=0; i<len; ++i) {
if (words[i] == word1 or words[i] == word2) {
if (words[i] == word1)
index1 = i;
if (words[i] == word2)
index2 = i;
if (index1 != INT_MAX and index2 != INT_MAX)
ans = min(ans, abs(index1 - index2));
}
}
return ans;
}
};
Runtime: 16 ms, faster than 73.88% of C++ online submissions for Shortest Word Distance.
Memory Usage: 11.9 MB, less than 90.79% of C++ online submissions for Shortest Word Distance.
