สมมติว่ามีคลาสที่ได้รับรายชื่อของคำใน Constructor จะมีวิธีการที่รับคำสองคำ word1 และ word2 และค้นหาระยะทางที่สั้นที่สุดระหว่างสองคำนี้ในรายการ เมธอดนั้นจะถูกเรียกซ้ำหลายครั้งด้วยพารามิเตอร์ต่างกัน
ให้เราถือว่าคำ =["ฝึกฝน", "ทำ", "สมบูรณ์แบบ", "ทักษะ", "ทำ"].
ดังนั้น หากอินพุตเป็นเหมือน word1 =“skill”, word2 =“practice” ผลลัพธ์จะเป็น 3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดหนึ่งแผนที่ m
-
ตัวเริ่มต้นใช้อาร์เรย์ของคำ
-
สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของคำ อัปเดต (เพิ่ม i ขึ้น 1) ทำ -
-
ใส่ i ต่อท้าย m[words[i]]
-
-
-
กำหนดฟังก์ชัน shortest() ซึ่งจะใช้ word1, word2,
-
กำหนดอาร์เรย์ arr1 :=m[word1]
-
กำหนดอาร์เรย์ arr2 :=m[word2]
-
ผม :=0, j :=0
-
ret :=อินฟินิตี้
-
ในขณะที่ (i <ขนาดของ arr1 และ j <ขนาดของ arr2) ทำ −
-
ret :=ขั้นต่ำของ ret และ |arr1[i] - arr2[j]|
-
ถ้า arr1[i]
-
(เพิ่ม i ขึ้น 1)
-
-
มิฉะนั้น
-
(เพิ่มขึ้น j โดย 1)
-
-
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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
