【双指针】面试题 17.11. 单词距离

面试题 17.11. 单词距离

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

示例：

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

提示：

words.length <= 100000

题解：

1. 先用list保存两个单词在words中出现的位置
2. 使用双指针，计算两个单词位置的最小距离

class Solution {
public int findClosest(String[] words, String word1, String word2) {
// 记录word1 和 word2 在 words中出现的位置
List<Integer> wps1 = new ArrayList<>();
List<Integer> wps2 = new ArrayList<>();
for (int i=0;i<words.length;++i) {
if (words[i].equals(word1)) {
wps1.add(i);
}
if (words[i].equals(word2)) {
wps2.add(i);
}
}
int p = 0;
int q = 0;
int minLen = Integer.MAX_VALUE;
// 使用双指针，对比两个word在words中出现的位置
while (p<wps1.size() && q<wps2.size()) {
int inxP = wps1.get(p);
int inxQ = wps2.get(q);
if (inxP > inxQ) {
if (minLen > inxP-inxQ) {
minLen = inxP-inxQ;
}
q++;
} else {
if (minLen > inxQ-inxP) {
minLen = inxQ-inxP;
}
p++;
}
}
return minLen;
}
}

最后

以上就是帅气翅膀为你收集整理的【双指针】面试题 17.11. 单词距离的全部内容，希望文章能够帮你解决【双指针】面试题 17.11. 单词距离所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。