数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++ 最短单词距离 II
假设有一个类，其构造函数接收一个单词列表，还有一个方法，该方法接收两个单词 word1 和 word2，并在列表中查找这两个单词之间的最短距离。该方法将被多次调用，参数不同。
让我们假设 words = ["practice", "makes", "perfect", "skill", "makes"]。
因此，如果输入为 word1 = “skill”，word2 = “practice”，则输出将为 3
为了解决这个问题，我们将遵循以下步骤：
定义一个映射 m
初始化器接收一个单词数组
对于初始化 i := 0，当 i < 单词大小，更新 (i 增加 1)，执行：
将 i 插入 m[words[i]] 的末尾
定义一个函数 shortest()，它将接收 word1、word2
定义一个数组 arr1 := m[word1]
定义一个数组 arr2 := m[word2]
i := 0，j := 0
ret := 无穷大
当 (i < arr1 大小 且 j < arr2 大小) 时，执行：
ret := ret 和 |arr1[i] - arr2[j]| 的最小值
如果 arr1[i] < arr2[j]，则：
(i 增加 1)
否则
(j 增加 1)
返回 ret
示例
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class WordDistance {
public:
unordered_map <string, vector <int< > m;
WordDistance(vector<string<& words) {
for(int i = 0; i < words.size(); i++){
m[words[i]].push_back(i);
}
}
int shortest(string word1, string word2) {
vector<int<& arr1 = m[word1];
vector<int<& arr2 = m[word2];
int i = 0;
int j = 0;
int ret = INT_MAX;
while (i < arr1.size() && j < arr2.size()) {
ret = min(ret, abs(arr1[i] - arr2[j]));
if (arr1[i] < arr2[j]) {
i++;
}
else
j++;
}
return ret;
}
};
main(){
vector<string< v = {"practice", "makes", "perfect", "skill","makes"};
WordDistance ob(v);
cout << (ob.shortest("skill", "practice")) << endl;
cout << (ob.shortest("makes", "skill"));
}输入
{"practice", "makes", "perfect", "skill", "makes"}
Call shortest("skill", "practice")
Call shortest("makes", "skill")输出
3 1
更新于：2020年11月18日
301 次浏览
广告