C++-এ শর্টেস্ট ওয়ার্ড ডিস্ট্যান্স II

একটি ক্লাস আছে যা কনস্ট্রাক্টরে ওয়ার্ড লিস্ট গ্রহণ করে। এর একটি মেথড আছে যা দুটি ওয়ার্ড word1 ও word2 নেবে এবং লিস্টে তাদের ন্যূনতম দূরত্ব বের করবে। এই মেথডটি বারবার কল হবে ভিন্ন প্যারামিটার দিয়ে।

যেমন, words = ["practice", "makes", "perfect", "skill", "makes"] হলে, word1 = "skill", word2 = "practice" এর জন্য আউটপুট হবে 3

সমাধানের ধাপগুলো:

একটি ম্যাপ m ডিফাইন করব
ইনিশিয়ালাইজারে ওয়ার্ড লিস্ট নেবে:
- প্রতি ওয়ার্ডের ইনডেক্স m[word] এ স্টোর করব
shortest() ফাংশন ডিফাইন করব:
- arr1 := m[word1], arr2 := m[word2]
- দুটি পয়েন্টার i, j দিয়ে ট্রায়ভার্স করব
- ret := infinity
- যখন i < arr1.size() && j < arr2.size():
  - ret := min(ret, |arr1[i] - arr2[j]|)
  - যদি arr1[i] < arr2[j] হয় তবে i++, অন্যথায় 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, 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;
    }
};

int 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