Description
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.
Solution
Three-pointer, time O(n), space O(1)
从左到右扫描，记录word1和word2的最新位置，比较两个最新位置的距离与最短距离。
class Solution {
public int shortestDistance(String[] words, String word1, String word2) {
int i = -1;
int j = -1;
int minDis = Integer.MAX_VALUE;
for (int k = 0; k < words.length; ++k) {
if (word1.equals(words[k])) {
i = k;
} else if (word2.equals(words[k])) {
j = k;
}
if (i != -1 && j != -1) {
minDis = Math.min(minDis, Math.abs(i - j));
}
}
return minDis;
}
}
