题目描述

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list. Your method will be called repeatedly many times with different parameters.

样例

Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “coding”, word2 = “practice”
Output: 3
Input: word1 = "makes", word2 = "coding"
Output: 1

算法1

(暴力枚举) $O(n^2)$

用hashmap记录每个单词的index，两重循环找最小的index差值

时空复杂度

暴力枚举，时间复杂度为O（n^2）
hashmap记录每个单词，空间复杂度为O（n）

参考文献

C++ 代码

class WordDistance {
public:
    WordDistance(vector<string>& words) {
        for(int i=0;i<words.size();i++)
        {
            m[words[i]].push_back(i);
        }
    }

    int shortest(string word1, string word2) {
        int res=INT_MAX;
        for(auto a:m[word1])
            for(auto b:m[word2])
            {
                res=min(res,abs(a-b));
            }
        return res;
    }
private:
    unordered_map<string,vector<int>> m;
};

算法2

(二分查找) $O(nlogn)$

用lower_bound二分查找不小于target值的位置，update最小差值

时间复杂度

lower_bound二分查找
空间复杂度o(n)

参考文献

C++ 代码

class WordDistance {
public:
    WordDistance(vector<string>& words) {
        for(int i=0;i<words.size();i++)
        {
            m[words[i]].push_back(i);
        }
    }

    int shortest(string word1, string word2) {
        int res=INT_MAX;
        for(auto a:m[word1])
        {
            auto b=m[word2];
            auto it=lower_bound(b.begin(), b.end(),a);
            if(it==b.end()) 
                res=min(res, a-b.back());
            else if(it==b.begin())
                res=min(res, b[0]-a);
            else
                res=min(res, min(a-*prev(it), *it-a));            
        }
        return res;
    }
private:
    unordered_map<string,vector<int>> m;
};