leetcode243--Shortest Word Distance

leetcode243--Shortest Word Distance

题目

这个题目的意思是给定了个单词数组,里面有很多的单词,可能会有重复的,然后再给定两个不相同的单词,结果是求这两个单词在这个数组中的最小距离,距离就是abs(idx1-idx2),

解决办法

  • 最容易想到的是,遍历一次数组,用两个新的数组记录这两个单词出现的位置,然后再找最小的距离 ,
class Solution:
public:
    int shortestDistance(vector<string>& words, string word1, string word2){

    vector<int> idx1, idx2;   //用来存他们的id的
    int res = INT_MAX; //用来记录最短距离

    for(int i=0;i<words.size(); ++i){
        if(words[i]==word1) idx1.push_back(i);
        else if(words[i]==word2) idx2.push_back(i);

    }

    // 求最小距离

    for(int i=0;i<idx1.size();++i){
        for(int j=0;j<idx2.size();++j){
            res = min(res, abs(idx1[i]-idx2[j]));
        }
    }

    return res;
};

其实写完之后就发现可以优化,因为可以边存边更新这个最小的距离。只需要用两个东西来记录是否读到就可以了。

class Solution{
public:
    int shortestDistance(vector<string>& words, string word1, string word2){
        int p1=-1,p2=-1, res=INT_MAX;
        for(int i=0;i<words.size();++i){
            if(words[i]==word1) p1=i;
            else if(words[i]==word2) p2=i;
            if(p1 != -1 && p2 != -1) res = min(res, abs(p1-p2));

        }

        return res;

    }
};

上面的写完之后,又思考了一下,可以减少一个p2, 不过要多加一个判断,即每次要看新的词,是不是和上一次的那个词一样,如果不一样就更新距离。这样每次算的都是相对来说离的比较近的这两个单词之前的距离。

class Solution{
public:
    int shortestDistance(vector<string>& words, string word1, string word2){
        int idx = -1, res = INT_MAX;
        for(int i=0;i<words.size();++i){
            if(words[i]==word1 || words[i] == word2){
                if(idx != -1 && words[i] != words[idx]) res=min(res, abs(idx-i));
                idx = i;
            }
        }

    }
}

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦