Khoảng cách từ ngắn nhất III trong C ++

Giả sử chúng ta có một danh sách các từ và hai từ khác được gọi là word1 và word2, chúng ta phải tìm khoảng cách ngắn nhất giữa hai từ này trong danh sách. Ở đây word1 và word2 có thể giống nhau và chúng đại diện cho hai từ riêng lẻ trong danh sách. Chúng ta hãy giả định rằng các từ =["practice", "make", "perfect", "skill", "make"].

Vì vậy, nếu đầu vào là word1 =“make”, word2 =“skill”, thì đầu ra sẽ là 1

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=10 ^ 9, l1:=10 ^ 9, l2:=-10 ^ 9

• n:=kích thước của từ

• để khởi tạo i:=0, khi i

  • nếu các từ [i] giống với từ1, thì -

    • l1:=i

  • nếu các từ [i] giống với từ 2, thì -

    • nếu word1 giống word2 thì -

      • l1:=l2

    • l2:=i

  • ret:=tối thiểu của | l2 - l1 | và ret

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int shortestWordDistance(vector<string<& words, string word1, string word2) {
      int ret = 1e9;
      int l1 = 1e9;
      int l2 = -1e9;
      int n = words.size();
      for (int i = 0; i < n; i++) {
         if (words[i] == word1) {
            l1 = i;
         }
         if (words[i] == word2) {
            if (word1 == word2) {
               l1 = l2;
            }
            l2 = i;
         }
         ret = min(abs(l2 - l1), ret);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string< v = {"practice", "makes", "perfect", "skill", "makes"};
   cout << (ob.shortestWordDistance(v, "makes", "skill"));
}

Đầu vào

{"practice", "makes", "perfect", "skill", "makes"},"makes", "skill"

Đầu ra

1