1.题目描述

面试题 17.11. 单词距离

有个内含单词的超大文本文件，给定任意两个不同的单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?

示例：

输入：words = [“I”,“am”,“a”,“student”,“from”,“a”,“university”,“in”,“a”,“city”], word1 = “a”, word2 = “student”
输出：1

2.解题思路与代码

2.1 解题思路

这道题使用双指针进行解答。使用 first 来寻找 word1，使用 second 来寻找 word2，当 first 找到 word1之后 first 暂停，然后开始移动 second 寻找 word2，找到 word2 之后 second 暂停。此时 first 和 second相减便是当前选找到的 word1 和 word2 的距离。对比距离最小值之后，继续开始寻找下一轮，此时需要让在前面指针的先往前走一步，右边的指针不动，这样就可以找到下一组目标距离。以示例为例：

1. 初始化 first 和 second 指向 0 位置
   
2. first 先移动开始寻找 word1，找到第一个word1 后停止
   
3. second 开始寻找 word2，找到第一个 word2 后停止，此时计算 first 和 second 之间的距离为 1
   
4. 此时first在前面，于是 first 继续寻找下一个 word1，寻找到后停止。此时计算 first 和 second 之间的距离为 2
   
5. 此时 second 在前面，于是开始移动 second 寻找下一个 word2，直到遍历完数组也没找到，遍历结束，返回最小值 1
   

2.2 代码

class Solution {    public int findClosest(String[] words, String word1, String word2) { int first = 0; int second = 0; int min = Integer.MAX_VALUE; boolean firstGo = true; while (first < words.length && second < words.length) {     while (firstGo) {  if(first >= words.length){      return min;  }  if (word1.equals(words[first])) {      firstGo = false;  } else {      first++;  }     }     while (!firstGo ) {  if (second >= words.length){      return min;  }  if (word2.equals(words[second])) {      firstGo = true;  } else {      second++;  }     }     min = Math.min(min, Math.abs(first - second));     if (first < second) {  first++;     } else {  second++;     } } return min;    }}

2.3 测试结果

通过测试

3.总结

• 这道题使用双指针寻找两个字符串
• 当找到两个字符串后，计算距离，然后开始下一轮寻找
• 下一轮开始时，只移动位于前面的指针，后面的指针不动，即用前面的指针去寻找字符串

虫部落快搜