原文链接: https://leetcode-cn.com/problems/find-closest-lcci

英文原文

You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. If the operation will be repeated many times for the same file (but different pairs of words), can you optimize your solution?

Example:

Input: words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"
Output: 1

Note:

• words.length <= 100000

中文题目

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

示例：

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

提示：

• words.length <= 100000

通过代码

高赞题解

扫一遍集合，记录word1和word2上一次出现位置，扫到word1或者word2时更新答案。
时间复杂度：O（n） 空间复杂度：O（1）

class Solution {
    const int INF=(1LL<<31)-1;
public:
    int findClosest(vector<string>& words, string word1, string word2) {
        int n=words.size();
        int Ans=INF;
        int a=-1,b=-1;
        for (int i=0;i<n;++i)
        {
            if (words[i]==word1)
            {
                a=i;
                if (b!=-1) Ans=min(Ans,a-b);
            }
            else if (words[i]==word2)
            {
                b=i;
                if (a!=-1) Ans=min(Ans,b-a);
            }
        }
        return Ans;
    }
};

统计信息

通过次数	提交次数	AC比率
15050	21920	68.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言