C ++中最短的字距II
假设有一个类在构造函数中接收单词列表，那么将有一个方法接收两个单词word1和word2并在列表中找到这两个单词之间的最短距离。该方法将使用不同的参数多次重复调用。
让我们假设单词=[“练习”，“成功”，“完美”，“技能”，“成功”]。
因此，如果输入像word1=“skill”，word2=“practice”，则输出为3
为了解决这个问题，我们将遵循以下步骤-
定义一张映射
初始化程序需要一个单词数组
在m[words[i]]的末尾插入i
对于初始化i：=0，当i<字长时，更新（将i增加1），执行-
定义一个函数shortest()，它将使用word1，word2，
定义一个数组arr1：=m[word1]
定义一个数组arr2：=m[word2]
i：=0，j：=0
ret：=无穷大
而（i<arr1的大小而j<arr2的大小），做-
（将j增加1）
（将i增加1）
ret：=ret和|arr1[i]-arr2[j]|的最小值
如果arr1[i]<arr2[j]，则-
除此以外
返回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