ধরুন আমাদের একটি স্ট্রিং, s, এবং আমাদের কাছে কয়েকটি শব্দ সহ আরেকটি তালিকা রয়েছে, এই শব্দগুলি একই দৈর্ঘ্যের। আমাদেরকে s-তে সাবস্ট্রিং(গুলি) এর সমস্ত প্রারম্ভিক সূচকগুলি খুঁজে বের করতে হবে যা শব্দের প্রতিটি শব্দের সংযোজন ঠিক একবার এবং কোনও হস্তক্ষেপকারী অক্ষর ছাড়াই৷
সুতরাং ইনপুট যদি হয় “wordgoodgoodgoodword” এবং শব্দগুলো হয় ["word","good"], তাহলে আউটপুট হবে [0,12]। এর কারণ হল সূচক 0 এবং 12 থেকে শুরু হওয়া সাবস্ট্রিং হল "ওয়ার্ডগুড" এবং "গুডওয়ার্ড"।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ok() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি স্ট্রিং s, ম্যাপ wordCnt এবং n −
লাগবে -
s-এর একটি অনুলিপি temp এ তৈরি করুন
-
i এর জন্য n থেকে s - 1
এর পরিসরে-
যদি তাপমাত্রার আকার 0 এর একাধিক হয়, তাহলে
-
যদি wordCnt-এ temp উপস্থিত না থাকে, তাহলে মিথ্যা ফেরত দিন
-
অন্যথায়
-
যদি wordCnt[temp] 1 হয়, তাহলে wordCnt থেকে temp মুছে দিন, temp একটি খালি স্ট্রিং হিসাবে সেট করুন
-
অন্যথায় wordCnt[temp] এর মান 1 দ্বারা কমিয়ে দিন, temp খালি স্ট্রিং হিসাবে সেট করুন।
-
-
-
s[i>
দ্বারা তাপমাত্রা বাড়ান
-
-
যদি টেম্প wordCnt-এ না থাকে, তাহলে মিথ্যা ফেরত দিন
-
অন্যথায়
-
যদি wordCnt[temp] 1 হয়, তাহলে wordCnt থেকে temp মুছে দিন, temp একটি খালি স্ট্রিং হিসাবে সেট করুন
-
অন্যথায় wordCnt[temp] এর মান 1 দ্বারা কমিয়ে দিন, temp খালি স্ট্রিং হিসাবে সেট করুন।
-
-
wordCnt-এর আকার 0
হলে true রিটার্ন করুন -
মূল পদ্ধতি থেকে, এটি করুন
-
যদি a এর আকার 0 হয়, বা b এর আকার 0 হয়, তাহলে খালি অ্যারে ফেরত দিন
-
একটি মানচিত্র wordCnt তৈরি করুন, b-এ উপস্থিত স্ট্রিংগুলির ফ্রিকোয়েন্সি wordCnt
-এ সংরক্ষণ করুন -
ans
নামে একটি অ্যারে তৈরি করুন -
window :=শব্দের সংখ্যা x প্রতিটি শব্দে অক্ষরের সংখ্যা
-
স্ট্রিং-এর একটি কপি তৈরি করুন a in temp
-
i এর জন্য রেঞ্জ উইন্ডোতে a – 1
এর আকার-
যদি টেম্প সাইজ উইন্ডো দ্বারা বিভাজ্য হয় এবং ঠিক আছে (temp, wordCnt, b[0] এর সাইজ), তাহলে
-
ans
-এ i – উইন্ডো সন্নিবেশ করুন
-
-
temp
এ একটি [i] সন্নিবেশ করান -
যদি temp> উইন্ডোর আকার হয়, তাহলে 0, 1
থেকে সাবস্ট্রিং মুছে দিন
-
-
যদি টেম্প সাইজ উইন্ডো দ্বারা বিভাজ্য হয় এবং ঠিক আছে (temp, wordCnt, b[0] এর সাইজ), তাহলে
-
উত্তরের মধ্যে একটি – উইন্ডোর আকার সন্নিবেশ করুন
-
-
উত্তর ফেরত দিন
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
bool ok(string s, unordered_map <string, int> wordCnt, int n){
string temp = "";
for(int i = 0; i < n; i++){
temp += s[i];
}
for(int i = n; i < s.size(); i++){
if(temp.size() % n == 0){
if(wordCnt.find(temp) == wordCnt.end())return false;
else{
if(wordCnt[temp] == 1){
wordCnt.erase(temp);
temp = "";
} else {
wordCnt[temp]--;
temp = "";
}
}
}
temp += s[i];
}
if(wordCnt.find(temp) == wordCnt.end())return false;
else{
if(wordCnt[temp] == 1){
wordCnt.erase(temp);
temp = "";
} else {
wordCnt[temp]--;
temp = "";
}
}
return wordCnt.size() == 0;
}
vector<int>findSubstring(string a, vector<string> &b) {
if(a.size() == 0 || b.size() == 0)return {};
unordered_map <string, int> wordCnt;
for(int i = 0; i < b.size(); i++)wordCnt[b[i]]++;
vector <int> ans;
int window = b.size() * b[0].size();
string temp ="";
for(int i = 0; i < window; i++)temp += a[i];
for(int i = window; i < a.size(); i++){
if(temp.size() % window == 0 && ok(temp, wordCnt, b[0].size())){
ans.push_back(i - window);
}
temp += a[i];
if(temp.size() > window)temp.erase(0, 1);
}
if(temp .size() % window ==0 && ok(temp, wordCnt, b[0].size()))ans.push_back(a.size() - window);
return ans;
}
};
main(){
vector<string> v = {"word","good"};
Solution ob;
print_vector(ob.findSubstring("wordgoodgoodgoodword", v));
} ইনপুট
“wordgoodgoodgoodword”, {"word","good"} আউটপুট
[0, 12, ]
