मान लीजिए एक क्लास है जो कंस्ट्रक्टर में शब्दों की सूची प्राप्त करती है, इसमें एक मेथड होगा जो दो शब्द word1 और word2 लेगा और सूची में इन दो शब्दों के बीच की सबसे छोटी दूरी ढूंढेगा। वह मेथड अलग-अलग पैरामीटर्स के साथ बार-बार कई बार कॉल किया जाएगा।
मान लीजिए words = ["practice", "makes", "perfect", "skill", "makes"]।
इसलिए, यदि इनपुट है word1 = "skill", word2 = "practice", तो आउटपुट 3 होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक मैप m परिभाषित करें
इनिशियलाइज़र शब्दों का ऐरे लेता है
i := 0 से शुरू करें, जब i < words का आकार, i बढ़ाते हुए, करें -
i को m[words[i]] के अंत में डालें
एक फ़ंक्शन shortest() परिभाषित करें, जो word1, word2 लेगा,
एक ऐरे arr1 := m[word1] परिभाषित करें
एक ऐरे arr2 := m[word2] परिभाषित करें
i := 0, j := 0
ret := इन्फिनिटी
जब (i < arr1 का आकार और j < arr2 का आकार), करें -
ret := min(ret, |arr1[i] - arr2[j]|)
यदि arr1[i] < arr2[j], तो -
(i को 1 से बढ़ाएं)
अन्यथा
(j को 1 से बढ़ाएं)
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
