Giả sử có một lớp nhận danh sách các từ trong hàm tạo, sẽ có một phương thức nhận hai từ word1 và word2 và tìm khoảng cách ngắn nhất giữa hai từ này trong danh sách. Phương thức đó sẽ được gọi lặp lại nhiều lần với các tham số khác nhau.
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 =“kỹ năng”, word2 =“thực hành”, thì đầu ra sẽ là 3
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một bản đồ m
-
Trình khởi tạo nhận một mảng các từ
-
để khởi tạo i:=0, khi tôi
-
chèn i vào cuối m [words [i]]
-
-
-
Xác định một hàm ngắn nhất (), hàm này sẽ nhận word1, word2,
-
Xác định mảng arr1:=m [word1]
-
Xác định mảng arr2:=m [word2]
-
i:=0, j:=0
-
ret:=infinity
-
while (i
-
ret:=tối thiểu ret và | arr1 [i] - arr2 [j] |
-
nếu arr1 [i]
-
(tăng tôi lên 1)
-
-
Nếu không
-
(tăng j lên 1)
-
-
-
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 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"));
} Đầu vào
{"practice", "makes", "perfect", "skill", "makes"}
Call shortest("skill", "practice")
Call shortest("makes", "skill") Đầu ra
3 1