C ++中最短的字距II

  • Z时代
  • 2024-01-10
  • 分类：综合

假设有一个类在构造函数中接收单词列表，那么将有一个方法接收两个单词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

      以上是 C ++中最短的字距II 的全部内容， 来源链接： utcz.com/z/330848.html

      回到顶部