题目描述

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

样例

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)$

与244(频繁调用)的区别是时间复杂度的要求不一样。遍历数组，将string存入hashmap，update最小index距离。

时间复杂度

时间O(n)
空间O(n)

参考文献

C++ 代码

class Solution {
public:
    int shortestDistance(vector<string>& words, string word1, string word2) {
        unordered_map<string,int> m;
        int res=INT_MAX;
        for(int i=0;i<words.size();i++)
        {
            m[words[i]]=i;
            if(m.count(word1) && words[i]==word2)
            {
                res=min(res,i-m[word1]);
            }
            else if(m.count(word2) && words[i]==word1) 
            {
                res=min(res,i-m[word2]);
            }
        }
        return res;
    }
};