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:
记得这是当时看MS面筋碰到的题,当时不会做,看了别人的思路。现在可以回想起别人的思路并写出来了。
遍历整个数组并用两个指针分别指向遍历时最新遇到的word1 和 word2,并且每次迭代都计算一次距离,并判断是否更新最小距离minDistance。这个思路计算的每个距离都是相邻的word1和word2之间的距离(相邻表示word1 和 word2 之间没有其它word1 或者word2),原因是最短距离一定出现在相邻的word1 / word2之间。
public class Solution
{
public int shortestDistance(String[] words, String word1, String word2)
{
if(words.length == 0 && word1 == null && word2 == null)
return 0;
int p1 = -1;
int p2 = -1;
int minDistance = words.length - 1;
for(int i = 0; i < words.length; i ++)
{
if(words[i].equals(word1))
p1 = i;
if(words[i].equals(word2))
p2 = i;
if(p1 >= 0 && p2 >= 0 && Math.abs(p1 - p2) < minDistance)
minDistance = Math.abs(p1 - p2);
}
return minDistance;
}
}