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