Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[LeetCode] 245. Shortest Word Distance III #245

Open
grandyang opened this issue May 30, 2019 · 2 comments
Open

[LeetCode] 245. Shortest Word Distance III #245

grandyang opened this issue May 30, 2019 · 2 comments

Comments

@grandyang
Copy link
Owner

grandyang commented May 30, 2019

 

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

word1  and  word2  may be the same and they represent two individual words in the list.

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

Input: _word1_ = “makes”, _word2_ = “coding”
Output: 1



Input: _word1_ = "makes", _word2_ = "makes"
Output: 3

Note:
You may assume  word1  and  word2  are both in the list.

 

这道题还是让我们求最短单词距离,有了之前两道题 Shortest Word Distance II 和 Shortest Word Distance 的基础,就大大降低了题目本身的难度。这里增加了一个条件,就是说两个单词可能会相同,所以在第一题中的解法的基础上做一些修改,博主最先想的解法是基于第一题中的解法二,由于会有相同的单词的情况,那么 p1 和 p2 就会相同,这样结果就会变成0,显然不对,所以要对 word1 和 word2 是否的相等的情况分开处理,如果相等了,由于 p1 和 p2 会相同,所以需要一个变量t来记录上一个位置,这样如果t不为 -1,且和当前的 p1 不同,可以更新结果,如果 word1 和 word2 不等,那么还是按原来的方法做,参见代码如下:

 

解法一:

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

 

上述代码其实可以优化一下,我们并不需要变量t来记录上一个位置,将 p1 初始化为数组长度,p2 初始化为数组长度的相反数,然后当 word1 和 word2 相等的情况,用 p1 来保存 p2 的结果,p2 赋为当前的位置i,这样就可以更新结果了,如果 word1 和 word2 不相等,则还跟原来的做法一样,这种思路真是挺巧妙的,参见代码如下:

 

解法二:

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

 

我们再来看一种更进一步优化的方法,只用一个变量 idx,这个 idx 的作用就相当于记录上一次的位置,当前 idx 不等 -1 时,说明当前i和 idx 不同,然后在 word1 和 word2 相同或者 words[i] 和 words[idx] 相同的情况下更新结果,最后别忘了将 idx 赋为i,参见代码如下;

 

解法三:

class Solution {
public:
    int shortestWordDistance(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 && (word1 == word2 || words[i] != words[idx])) {
                    res = min(res, i - idx);
                }
                idx = i;
            }
        }
        return res;
    }
};

 

Github 同步地址:

#245

 

类似题目:

Shortest Word Distance II

Shortest Word Distance

 

参考资料:

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

https://leetcode.com/problems/shortest-word-distance-iii/discuss/67097/12-16-lines-Java-C%2B%2B

https://leetcode.com/problems/shortest-word-distance-iii/discuss/67095/Short-Java-solution-10-lines-O(n)-modified-from-Shortest-Word-Distance-I

 

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

 

@LukLau
Copy link

LukLau commented Dec 27, 2019

疑惑

🤔 解法一

// t != p1 应该多余吧
 if (word1 == word2 && t != -1 && t != p1) {
                    res = min(res, abs(t - p1));
                } else if (p1 != p2) {
                    res = min(res, abs(p1 - p2));
                }

@grandyang
Copy link
Owner Author

不加会出错,比如下面这个例子:

["a","c","a","a"]
"a"
"a"

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants