243. Shortest Word Distance

 

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

Note:
You may assume that  word1  does not equal to  word2 , and  word1  and  word2  are both in the list.

 

这道题给了我们一个单词数组,又给定了两个单词,让求这两个单词之间的最小距离,限定了两个单词不同,而且都在数组中。博主最先想到的方法比较笨,是要用 HashMap 来做,建立每个单词和其所有出现位置数组的映射,但是后来想想,反正建立映射也要遍历一遍数组,还不如直接遍历一遍数组,直接把两个给定单词所有出现的位置分别存到两个数组里,然后再对两个数组进行两两比较更新结果,参见代码如下:

 

解法一:

class Solution {
public:
    int shortestDistance(vector<string>& words, string word1, string word2) {
        vector<int> idx1, idx2;
        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;
    }
};

 

上面的那种方法并不高效,其实需要遍历一次数组就可以了,用两个变量 p1,p2 初始化为 -1,然后遍历数组,遇到单词1,就将其位置存在 p1 里,若遇到单词2,就将其位置存在 p2 里,如果此时 p1, p2 都不为 -1 了,那么更新结果,参见代码如下:

 

解法二:

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;
    }
};

 

下面这种方法只用一个辅助变量 idx,初始化为 -1,然后遍历数组,如果遇到等于两个单词中的任意一个的单词,再看 idx 是否为 -1,若不为 -1,且指向的单词和当前遍历到的单词不同,更新结果,参见代码如下:

 

解法三:

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[idx] != words[i]) {
                    res = min(res, i - idx);
                }
                idx = i;
            }
        }
        return res;
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/243

 

类似题目:

Shortest Word Distance II

Shortest Word Distance III 

 

参考资料:

https://leetcode.com/problems/shortest-word-distance/

https://leetcode.com/problems/shortest-word-distance/discuss/66931/AC-Java-clean-solution

https://leetcode.com/problems/shortest-word-distance/discuss/66939/Java%3A-only-need-to-keep-one-index

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation