LeetCode 244. 最短单词距离 II（哈希map+set二分查找）
LeetCode 244. 最短单词距离 II（哈希map+set二分查找）
Michael阿明
发布于 2020-07-13 14:52:44
发布于 2020-07-13 14:52:44
文章被收录于专栏：Michael阿明学习之路
1. 题目
请设计一个类，使该类的构造函数能够接收一个单词列表。 然后再实现一个方法，该方法能够分别接收两个单词 word1 和 word2，并返回列表中这两个单词之间的最短距离。 您的方法将被以不同的参数调用 多次。
示例:
假设 words = ["practice", "makes", "perfect", "coding", "makes"]
输入: word1 = “coding”, word2 = “practice”
输出: 3
输入: word1 = "makes", word2 = "coding"
输出: 1注意: 你可以假设 word1 不等于 word2, 并且 word1 和 word2 都在列表里。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shortest-word-distance-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
类似题目：
LeetCode 243. 最短单词距离 LeetCode 245. 最短单词距离 III 程序员面试金典 - 面试题 17.11. 单词距离（multimap平衡二叉搜索树）
2.1 暴力超时
11 / 12 个通过测试用例
class WordDistance {
vector<string> w;
public:
WordDistance(vector<string>& words) {
w = words;
}
int shortest(string word1, string word2) {
int l = -1, r = -1, mindis = INT_MAX;
for(int i = 0; i < w.size(); ++i)
{
if(w[i] == word1)
l = i;
if(w[i] == word2)
r = i;
if(l != -1 && r != -1)
mindis = min(mindis, abs(l-r));
}
return mindis;
}
};2.2 哈希表+set二分查找
- 创建哈希map，单词是key，其位置是set
- 遍历其中一个单词的所有位置 i ，在另一个单词的set中二分查找 i 的前后位置
class WordDistance {
unordered_map<string,set<int>> m;
public:
WordDistance(vector<string>& words) {
for(int i = 0; i < words.size(); ++i)
{
m[words[i]].insert(i);
}
}
int shortest(string word1, string word2) {
int mindis = INT_MAX;
for(auto i = m[word1].begin(); i != m[word1].end(); ++i)
{
auto j = m[word2].lower_bound(*i);
if(j != m[word2].end())
mindis = min(mindis, abs(*j-*i));
if(j != m[word2].begin())
mindis = min(mindis, abs(*(--j)-*i));
}
return mindis;
}
};68 ms 19.6 MB
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/07/07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
